MacTech 1 to 12

home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / develop™ Technical Journal / develop Issue 28 code / Merge_Tools.sit / Merge Tools / analyze.c < prev next >
MacBinary | 1996-09-06 | 28.5 KB | [TEXT/MPS ]
open in:
MacOS 8.1 extracted |
Win98 extracted |
DOS extracted
browse contents |
view JSON data |
view as text

This file was processed as: MacBinary (archive/macBinary).
Confidence	Program	Detection	Match Type	Support
`66%`	dexvert	Compact Compressed (Unix) `(archive/compact)`	ext	Supported
`10%`	dexvert	MacBinary `(archive/macBinary)`	fallback	Supported
`1%`	dexvert	Text File `(text/txt)`	fallback	Supported
`100%`	file	MacBinary II, inited, Fri Sep 6 16:39:15 1996, modified Fri Sep 6 16:39:15 1996, creator 'MPS ', type ASCII, 28451 bytes "analyze.c" , at 0x6fa3 428 bytes resource	default (weak)
`99%`	file	data	default
`74%`	TrID	Macintosh plain text (MacBinary)	default
`25%`	TrID	MacBinary 2	default (weak)
`100%`	siegfried	fmt/1762 MacBinary (II)	default
`100%`	lsar	MacBinary	default
id metadata
key	value
macFileType	`[TEXT]`
macFileCreator	`[MPS ]`
hex view
+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 09 61 6e 61 6c 79 7a | 65 2e 63 00 00 00 00 00 |..analyz|e.c.....|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 4d 50 53 | 20 01 00 00 00 00 00 00 |.TEXTMPS| .......|
|00000050| 00 00 00 00 00 6f 23 00 | 00 01 ac ae 56 3c 73 ae |.....o#.|....V<s.|
|00000060| 56 3c 73 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |V<s.....|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 a8 00 00 00 |........|........|
|00000080| 2f 2a 20 41 6e 61 6c 79 | 7a 65 20 66 69 6c 65 20 |/* Analy|ze file |
|00000090| 64 69 66 66 65 72 65 6e | 63 65 73 20 66 6f 72 20 |differen|ces for |
|000000a0| 45 63 6c 65 63 74 75 73 | 20 69 6e 74 65 67 72 61 |Eclectus| integra|
|000000b0| 74 69 6f 6e 20 75 74 69 | 6c 69 74 69 65 73 2e 0d |tion uti|lities..|
|000000c0| 09 20 43 6f 70 79 72 69 | 67 68 74 20 28 43 29 20 |. Copyri|ght (C) |
|000000d0| 31 39 39 32 2d 39 36 20 | 45 63 6c 65 63 74 75 73 |1992-96 |Eclectus|
|000000e0| 20 28 44 2e 20 4a 6f 68 | 6e 20 41 6e 64 65 72 73 | (D. Joh|n Anders|
|000000f0| 6f 6e 2c 20 41 6c 61 6e | 20 42 2e 20 48 61 72 70 |on, Alan| B. Harp|
|00000100| 65 72 29 2e 0d 0d 54 68 | 69 73 20 66 69 6c 65 20 |er)...Th|is file |
|00000110| 69 73 20 70 61 72 74 20 | 6f 66 20 74 68 65 20 45 |is part |of the E|
|00000120| 63 6c 65 63 74 75 73 20 | 69 6e 74 65 67 72 61 74 |clectus |integrat|
|00000130| 69 6f 6e 20 75 74 69 6c | 69 74 69 65 73 2e 0d 0d |ion util|ities...|
|00000140| 45 63 6c 65 63 74 75 73 | 20 69 6e 74 65 67 72 61 |Eclectus| integra|
|00000150| 74 69 6f 6e 20 75 74 69 | 6c 69 74 69 65 73 20 61 |tion uti|lities a|
|00000160| 72 65 20 66 72 65 65 20 | 73 6f 66 74 77 61 72 65 |re free |software|
|00000170| 3b 20 79 6f 75 20 63 61 | 6e 20 72 65 64 69 73 74 |; you ca|n redist|
|00000180| 72 69 62 75 74 65 0d 69 | 74 20 61 6e 64 2f 6f 72 |ribute.i|t and/or|
|00000190| 20 6d 6f 64 69 66 79 20 | 69 74 20 75 6e 64 65 72 | modify |it under|
|000001a0| 20 74 68 65 20 74 65 72 | 6d 73 20 6f 66 20 74 68 | the ter|ms of th|
|000001b0| 65 20 47 4e 55 20 47 65 | 6e 65 72 61 6c 20 50 75 |e GNU Ge|neral Pu|
|000001c0| 62 6c 69 63 20 4c 69 63 | 65 6e 73 65 0d 61 73 20 |blic Lic|ense.as |
|000001d0| 70 75 62 6c 69 73 68 65 | 64 20 62 79 20 74 68 65 |publishe|d by the|
|000001e0| 20 46 72 65 65 20 53 6f | 66 74 77 61 72 65 20 46 | Free So|ftware F|
|000001f0| 6f 75 6e 64 61 74 69 6f | 6e 3b 20 65 69 74 68 65 |oundatio|n; eithe|
|00000200| 72 20 76 65 72 73 69 6f | 6e 20 31 2c 20 6f 72 0d |r versio|n 1, or.|
|00000210| 28 61 74 20 79 6f 75 72 | 20 6f 70 74 69 6f 6e 29 |(at your| option)|
|00000220| 20 61 6e 79 20 6c 61 74 | 65 72 20 76 65 72 73 69 | any lat|er versi|
|00000230| 6f 6e 2e 0d 0d 45 63 6c | 65 63 74 75 73 20 69 6e |on...Ecl|ectus in|
|00000240| 74 65 67 72 61 74 69 6f | 6e 20 75 74 69 6c 69 74 |tegratio|n utilit|
|00000250| 69 65 73 20 69 73 20 64 | 69 73 74 72 69 62 75 74 |ies is d|istribut|
|00000260| 65 64 20 69 6e 20 74 68 | 65 20 68 6f 70 65 20 74 |ed in th|e hope t|
|00000270| 68 61 74 20 69 74 0d 77 | 69 6c 6c 20 62 65 20 75 |hat it.w|ill be u|
|00000280| 73 65 66 75 6c 2c 20 62 | 75 74 20 57 49 54 48 4f |seful, b|ut WITHO|
|00000290| 55 54 20 41 4e 59 20 57 | 41 52 52 41 4e 54 59 3b |UT ANY W|ARRANTY;|
|000002a0| 20 77 69 74 68 6f 75 74 | 20 65 76 65 6e 20 74 68 | without| even th|
|000002b0| 65 20 69 6d 70 6c 69 65 | 64 0d 77 61 72 72 61 6e |e implie|d.warran|
|000002c0| 74 79 20 6f 66 20 4d 45 | 52 43 48 41 4e 54 41 42 |ty of ME|RCHANTAB|
|000002d0| 49 4c 49 54 59 20 6f 72 | 20 46 49 54 4e 45 53 53 |ILITY or| FITNESS|
|000002e0| 20 46 4f 52 20 41 20 50 | 41 52 54 49 43 55 4c 41 | FOR A P|ARTICULA|
|000002f0| 52 20 50 55 52 50 4f 53 | 45 2e 0d 53 65 65 20 74 |R PURPOS|E..See t|
|00000300| 68 65 20 47 4e 55 20 47 | 65 6e 65 72 61 6c 20 50 |he GNU G|eneral P|
|00000310| 75 62 6c 69 63 20 4c 69 | 63 65 6e 73 65 20 66 6f |ublic Li|cense fo|
|00000320| 72 20 6d 6f 72 65 20 64 | 65 74 61 69 6c 73 2e 0d |r more d|etails..|
|00000330| 0d 59 6f 75 20 73 68 6f | 75 6c 64 20 68 61 76 65 |.You sho|uld have|
|00000340| 20 72 65 63 65 69 76 65 | 64 20 61 20 63 6f 70 79 | receive|d a copy|
|00000350| 20 6f 66 20 74 68 65 20 | 47 4e 55 20 47 65 6e 65 | of the |GNU Gene|
|00000360| 72 61 6c 20 50 75 62 6c | 69 63 20 4c 69 63 65 6e |ral Publ|ic Licen|
|00000370| 73 65 0d 61 6c 6f 6e 67 | 20 77 69 74 68 20 74 68 |se.along| with th|
|00000380| 65 20 45 63 6c 65 63 74 | 75 73 20 69 6e 74 65 67 |e Eclect|us integ|
|00000390| 72 61 74 69 6f 6e 20 75 | 74 69 6c 69 74 69 65 73 |ration u|tilities|
|000003a0| 3b 20 73 65 65 20 74 68 | 65 20 66 69 6c 65 20 43 |; see th|e file C|
|000003b0| 4f 50 59 49 4e 47 2e 0d | 49 66 20 6e 6f 74 2c 20 |OPYING..|If not, |
|000003c0| 77 72 69 74 65 20 74 6f | 20 74 68 65 20 46 72 65 |write to| the Fre|
|000003d0| 65 20 53 6f 66 74 77 61 | 72 65 20 46 6f 75 6e 64 |e Softwa|re Found|
|000003e0| 61 74 69 6f 6e 2c 20 36 | 37 35 20 4d 61 73 73 20 |ation, 6|75 Mass |
|000003f0| 41 76 65 2c 20 43 61 6d | 62 72 69 64 67 65 2c 0d |Ave, Cam|bridge,.|
|00000400| 4d 41 20 30 32 31 33 39 | 2c 20 55 53 41 2e 09 2a |MA 02139|, USA..*|
|00000410| 2f 0d 0d 2f 2a 20 54 68 | 65 20 62 61 73 69 63 20 |/../* Th|e basic |
|00000420| 61 6c 67 6f 72 69 74 68 | 6d 20 69 73 20 64 65 73 |algorith|m is des|
|00000430| 63 72 69 62 65 64 20 69 | 6e 3a 0d 20 20 20 22 41 |cribed i|n:.   "A|
|00000440| 6e 20 4f 28 4e 44 29 20 | 44 69 66 66 65 72 65 6e |n O(ND) |Differen|
|00000450| 63 65 20 41 6c 67 6f 72 | 69 74 68 6d 20 61 6e 64 |ce Algor|ithm and|
|00000460| 20 69 74 73 20 56 61 72 | 69 61 74 69 6f 6e 73 22 | its Var|iations"|
|00000470| 2c 20 45 75 67 65 6e 65 | 20 4d 79 65 72 73 2c 0d |, Eugene| Myers,.|
|00000480| 20 20 20 41 6c 67 6f 72 | 69 74 68 6d 69 63 61 20 |   Algor|ithmica |
|00000490| 56 6f 6c 2e 20 31 20 4e | 6f 2e 20 32 2c 20 31 39 |Vol. 1 N|o. 2, 19|
|000004a0| 38 36 2c 20 70 70 2e 20 | 32 35 31 2d 32 36 36 3b |86, pp. |251-266;|
|000004b0| 0d 20 20 20 73 65 65 20 | 65 73 70 65 63 69 61 6c |.   see |especial|
|000004c0| 6c 79 20 73 65 63 74 69 | 6f 6e 20 34 2e 32 2c 20 |ly secti|on 4.2, |
|000004d0| 77 68 69 63 68 20 64 65 | 73 63 72 69 62 65 73 20 |which de|scribes |
|000004e0| 74 68 65 20 76 61 72 69 | 61 74 69 6f 6e 20 75 73 |the vari|ation us|
|000004f0| 65 64 20 62 65 6c 6f 77 | 2e 0d 20 20 20 55 6e 6c |ed below|..   Unl|
|00000500| 65 73 73 20 74 68 65 20 | 2d 2d 6d 69 6e 69 6d 61 |ess the |--minima|
|00000510| 6c 20 6f 70 74 69 6f 6e | 20 69 73 20 73 70 65 63 |l option| is spec|
|00000520| 69 66 69 65 64 2c 20 74 | 68 69 73 20 63 6f 64 65 |ified, t|his code|
|00000530| 20 75 73 65 73 20 74 68 | 65 20 54 4f 4f 5f 45 58 | uses th|e TOO_EX|
|00000540| 50 45 4e 53 49 56 45 0d | 20 20 20 68 65 75 72 69 |PENSIVE.|   heuri|
|00000550| 73 74 69 63 2c 20 62 79 | 20 50 61 75 6c 20 45 67 |stic, by| Paul Eg|
|00000560| 67 65 72 74 2c 20 74 6f | 20 6c 69 6d 69 74 20 74 |gert, to| limit t|
|00000570| 68 65 20 63 6f 73 74 20 | 74 6f 20 4f 28 4e 2a 2a |he cost |to O(N**|
|00000580| 31 2e 35 20 6c 6f 67 20 | 4e 29 0d 20 20 20 61 74 |1.5 log |N).   at|
|00000590| 20 74 68 65 20 70 72 69 | 63 65 20 6f 66 20 70 72 | the pri|ce of pr|
|000005a0| 6f 64 75 63 69 6e 67 20 | 73 75 62 6f 70 74 69 6d |oducing |suboptim|
|000005b0| 61 6c 20 6f 75 74 70 75 | 74 20 66 6f 72 20 6c 61 |al outpu|t for la|
|000005c0| 72 67 65 20 69 6e 70 75 | 74 73 20 77 69 74 68 0d |rge inpu|ts with.|
|000005d0| 20 20 20 6d 61 6e 79 20 | 64 69 66 66 65 72 65 6e |   many |differen|
|000005e0| 63 65 73 2e 0d 0d 20 20 | 20 54 68 65 20 62 61 73 |ces...  | The bas|
|000005f0| 69 63 20 61 6c 67 6f 72 | 69 74 68 6d 20 77 61 73 |ic algor|ithm was|
|00000600| 20 69 6e 64 65 70 65 6e | 64 65 6e 74 6c 79 20 64 | indepen|dently d|
|00000610| 69 73 63 6f 76 65 72 65 | 64 20 61 73 20 64 65 73 |iscovere|d as des|
|00000620| 63 72 69 62 65 64 20 69 | 6e 3a 0d 20 20 20 22 41 |cribed i|n:.   "A|
|00000630| 6c 67 6f 72 69 74 68 6d | 73 20 66 6f 72 20 41 70 |lgorithm|s for Ap|
|00000640| 70 72 6f 78 69 6d 61 74 | 65 20 53 74 72 69 6e 67 |proximat|e String|
|00000650| 20 4d 61 74 63 68 69 6e | 67 22 2c 20 45 2e 20 55 | Matchin|g", E. U|
|00000660| 6b 6b 6f 6e 65 6e 2c 0d | 20 20 20 49 6e 66 6f 72 |kkonen,.|   Infor|
|00000670| 6d 61 74 69 6f 6e 20 61 | 6e 64 20 43 6f 6e 74 72 |mation a|nd Contr|
|00000680| 6f 6c 20 56 6f 6c 2e 20 | 36 34 2c 20 31 39 38 35 |ol Vol. |64, 1985|
|00000690| 2c 20 70 70 2e 20 31 30 | 30 2d 31 31 38 2e 20 20 |, pp. 10|0-118.  |
|000006a0| 2a 2f 0d 0d 23 69 6e 63 | 6c 75 64 65 20 22 64 69 |*/..#inc|lude "di|
|000006b0| 66 66 2e 68 22 0d 23 69 | 6e 63 6c 75 64 65 20 3c |ff.h".#i|nclude <|
|000006c0| 6c 69 6d 69 74 73 2e 68 | 3e 0d 23 69 6e 63 6c 75 |limits.h|>.#inclu|
|000006d0| 64 65 20 3c 73 74 72 69 | 6e 67 2e 68 3e 0d 23 69 |de <stri|ng.h>.#i|
|000006e0| 6e 63 6c 75 64 65 20 3c | 73 74 64 6c 69 62 2e 68 |nclude <|stdlib.h|
|000006f0| 3e 0d 0d 73 74 61 74 69 | 63 20 69 6e 74 20 2a 78 |>..stati|c int *x|
|00000700| 76 65 63 2c 20 2a 79 76 | 65 63 3b 09 09 09 09 2f |vec, *yv|ec;..../|
|00000710| 2a 20 56 65 63 74 6f 72 | 73 20 62 65 69 6e 67 20 |* Vector|s being |
|00000720| 63 6f 6d 70 61 72 65 64 | 2e 20 2a 2f 0d 73 74 61 |compared|. */.sta|
|00000730| 74 69 63 20 69 6e 74 20 | 2a 66 64 69 61 67 3b 09 |tic int |*fdiag;.|
|00000740| 09 09 09 09 09 09 2f 2a | 20 56 65 63 74 6f 72 2c |....../*| Vector,|
|00000750| 20 69 6e 64 65 78 65 64 | 20 62 79 20 64 69 61 67 | indexed| by diag|
|00000760| 6f 6e 61 6c 2c 20 63 6f | 6e 74 61 69 6e 69 6e 67 |onal, co|ntaining|
|00000770| 0d 09 09 09 09 09 09 09 | 09 09 09 09 09 09 09 09 |........|........|
|00000780| 09 09 20 74 68 65 20 58 | 20 63 6f 6f 72 64 69 6e |.. the X| coordin|
|00000790| 61 74 65 20 6f 66 20 74 | 68 65 20 70 6f 69 6e 74 |ate of t|he point|
|000007a0| 20 66 75 72 74 68 65 73 | 74 0d 09 09 09 09 09 09 | furthes|t.......|
|000007b0| 09 09 09 09 09 09 09 09 | 09 09 09 20 61 6c 6f 6e |........|... alon|
|000007c0| 67 20 74 68 65 20 67 69 | 76 65 6e 20 64 69 61 67 |g the gi|ven diag|
|000007d0| 6f 6e 61 6c 20 69 6e 20 | 74 68 65 20 66 6f 72 77 |onal in |the forw|
|000007e0| 61 72 64 0d 09 09 09 09 | 09 09 09 09 09 09 09 09 |ard.....|........|
|000007f0| 09 09 09 09 09 20 73 65 | 61 72 63 68 20 6f 66 20 |..... se|arch of |
|00000800| 74 68 65 20 65 64 69 74 | 20 6d 61 74 72 69 78 2e |the edit| matrix.|
|00000810| 20 2a 2f 0d 73 74 61 74 | 69 63 20 69 6e 74 20 2a | */.stat|ic int *|
|00000820| 62 64 69 61 67 3b 09 09 | 09 09 09 09 09 2f 2a 20 |bdiag;..|...../* |
|00000830| 56 65 63 74 6f 72 2c 20 | 69 6e 64 65 78 65 64 20 |Vector, |indexed |
|00000840| 62 79 20 64 69 61 67 6f | 6e 61 6c 2c 20 63 6f 6e |by diago|nal, con|
|00000850| 74 61 69 6e 69 6e 67 0d | 09 09 09 09 09 09 09 09 |taining.|........|
|00000860| 09 09 09 09 09 09 09 09 | 09 20 74 68 65 20 58 20 |........|. the X |
|00000870| 63 6f 6f 72 64 69 6e 61 | 74 65 20 6f 66 20 74 68 |coordina|te of th|
|00000880| 65 20 70 6f 69 6e 74 20 | 66 75 72 74 68 65 73 74 |e point |furthest|
|00000890| 0d 09 09 09 09 09 09 09 | 09 09 09 09 09 09 09 09 |........|........|
|000008a0| 09 09 20 61 6c 6f 6e 67 | 20 74 68 65 20 67 69 76 |.. along| the giv|
|000008b0| 65 6e 20 64 69 61 67 6f | 6e 61 6c 20 69 6e 20 74 |en diago|nal in t|
|000008c0| 68 65 20 62 61 63 6b 77 | 61 72 64 0d 09 09 09 09 |he backw|ard.....|
|000008d0| 09 09 09 09 09 09 09 09 | 09 09 09 09 09 20 73 65 |........|..... se|
|000008e0| 61 72 63 68 20 6f 66 20 | 74 68 65 20 65 64 69 74 |arch of |the edit|
|000008f0| 20 6d 61 74 72 69 78 2e | 20 2a 2f 0d 0d 73 74 61 | matrix.| */..sta|
|00000900| 74 69 63 20 69 6e 74 20 | 74 6f 6f 5f 65 78 70 65 |tic int |too_expe|
|00000910| 6e 73 69 76 65 3b 09 09 | 09 09 2f 2a 20 45 64 69 |nsive;..|../* Edi|
|00000920| 74 20 73 63 72 69 70 74 | 73 20 6c 6f 6e 67 65 72 |t script|s longer|
|00000930| 20 74 68 61 6e 20 74 68 | 69 73 20 61 72 65 20 74 | than th|is are t|
|00000940| 6f 6f 0d 09 09 09 09 09 | 09 09 09 09 09 09 09 09 |oo......|........|
|00000950| 09 09 09 09 20 65 78 70 | 65 6e 73 69 76 65 20 74 |.... exp|ensive t|
|00000960| 6f 20 63 6f 6d 70 75 74 | 65 2e 20 20 2a 2f 0d 0d |o comput|e.  */..|
|00000970| 23 64 65 66 69 6e 65 20 | 53 4e 41 4b 45 5f 4c 49 |#define |SNAKE_LI|
|00000980| 4d 49 54 20 32 30 09 2f | 2a 20 53 6e 61 6b 65 73 |MIT 20./|* Snakes|
|00000990| 20 62 69 67 67 65 72 20 | 74 68 61 6e 20 74 68 69 | bigger |than thi|
|000009a0| 73 20 61 72 65 20 63 6f | 6e 73 69 64 65 72 65 64 |s are co|nsidered|
|000009b0| 20 60 62 69 67 27 2e 20 | 20 2a 2f 0d 0d 73 74 72 | `big'. | */..str|
|000009c0| 75 63 74 20 70 61 72 74 | 69 74 69 6f 6e 0d 7b 0d |uct part|ition.{.|
|000009d0| 20 20 69 6e 74 20 78 6d | 69 64 2c 20 79 6d 69 64 |  int xm|id, ymid|
|000009e0| 3b 09 2f 2a 20 4d 69 64 | 70 6f 69 6e 74 73 20 6f |;./* Mid|points o|
|000009f0| 66 20 74 68 69 73 20 70 | 61 72 74 69 74 69 6f 6e |f this p|artition|
|00000a00| 2e 20 20 2a 2f 0d 20 20 | 69 6e 74 20 6c 6f 5f 6d |.  */.  |int lo_m|
|00000a10| 69 6e 69 6d 61 6c 3b 09 | 2f 2a 20 4e 6f 6e 7a 65 |inimal;.|/* Nonze|
|00000a20| 72 6f 20 69 66 20 6c 6f | 77 20 68 61 6c 66 20 77 |ro if lo|w half w|
|00000a30| 69 6c 6c 20 62 65 20 61 | 6e 61 6c 79 7a 65 64 20 |ill be a|nalyzed |
|00000a40| 6d 69 6e 69 6d 61 6c 6c | 79 2e 20 20 2a 2f 0d 20 |minimall|y.  */. |
|00000a50| 20 69 6e 74 20 68 69 5f | 6d 69 6e 69 6d 61 6c 3b | int hi_|minimal;|
|00000a60| 09 2f 2a 20 4c 69 6b 65 | 77 69 73 65 20 66 6f 72 |./* Like|wise for|
|00000a70| 20 68 69 67 68 20 68 61 | 6c 66 2e 20 20 2a 2f 0d | high ha|lf.  */.|
|00000a80| 7d 3b 0d 0d 73 74 61 74 | 69 63 20 73 74 72 75 63 |};..stat|ic struc|
|00000a90| 74 20 63 68 61 6e 67 65 | 09 20 2a 61 64 64 5f 63 |t change|. *add_c|
|00000aa0| 68 61 6e 67 65 20 28 69 | 6e 74 20 6c 69 6e 65 30 |hange (i|nt line0|
|00000ab0| 2c 20 69 6e 74 20 6c 69 | 6e 65 31 2c 20 69 6e 74 |, int li|ne1, int|
|00000ac0| 20 64 65 6c 65 74 65 64 | 2c 20 69 6e 74 20 69 6e | deleted|, int in|
|00000ad0| 73 65 72 74 65 64 2c 20 | 73 74 72 75 63 74 20 63 |serted, |struct c|
|00000ae0| 68 61 6e 67 65 20 2a 6f | 6c 64 29 3b 0d 73 74 61 |hange *o|ld);.sta|
|00000af0| 74 69 63 20 73 74 72 75 | 63 74 20 63 68 61 6e 67 |tic stru|ct chang|
|00000b00| 65 09 20 2a 62 75 69 6c | 64 5f 73 63 72 69 70 74 |e. *buil|d_script|
|00000b10| 20 28 73 74 72 75 63 74 | 20 66 69 6c 65 5f 64 61 | (struct| file_da|
|00000b20| 74 61 20 2a 66 69 6c 65 | 30 50 74 72 2c 20 73 74 |ta *file|0Ptr, st|
|00000b30| 72 75 63 74 20 66 69 6c | 65 5f 64 61 74 61 20 2a |ruct fil|e_data *|
|00000b40| 66 69 6c 65 31 50 74 72 | 29 3b 0d 73 74 61 74 69 |file1Ptr|);.stati|
|00000b50| 63 20 76 6f 69 64 20 09 | 09 09 09 09 09 63 6f 6d |c void .|.....com|
|00000b60| 70 61 72 65 73 65 71 20 | 28 73 74 72 75 63 74 20 |pareseq |(struct |
|00000b70| 66 69 6c 65 5f 64 61 74 | 61 20 2a 66 69 6c 65 30 |file_dat|a *file0|
|00000b80| 50 74 72 2c 20 73 74 72 | 75 63 74 20 66 69 6c 65 |Ptr, str|uct file|
|00000b90| 5f 64 61 74 61 20 2a 66 | 69 6c 65 31 50 74 72 2c |_data *f|ile1Ptr,|
|00000ba0| 0d 09 09 09 09 09 09 09 | 09 09 09 09 09 09 09 09 |........|........|
|00000bb0| 09 09 09 69 6e 74 20 78 | 6f 66 66 2c 20 69 6e 74 |...int x|off, int|
|00000bc0| 20 78 6c 69 6d 2c 20 69 | 6e 74 20 79 6f 66 66 2c | xlim, i|nt yoff,|
|00000bd0| 20 69 6e 74 20 79 6c 69 | 6d 2c 20 69 6e 74 20 6d | int yli|m, int m|
|00000be0| 69 6e 69 6d 61 6c 29 3b | 0d 73 74 61 74 69 63 20 |inimal);|.static |
|00000bf0| 69 6e 74 09 09 09 09 09 | 09 09 64 69 61 67 20 28 |int.....|..diag (|
|00000c00| 69 6e 74 20 78 6f 66 66 | 2c 20 69 6e 74 20 78 6c |int xoff|, int xl|
|00000c10| 69 6d 2c 20 69 6e 74 20 | 79 6f 66 66 2c 20 69 6e |im, int |yoff, in|
|00000c20| 74 20 79 6c 69 6d 2c 20 | 69 6e 74 20 6d 69 6e 69 |t ylim, |int mini|
|00000c30| 6d 61 6c 2c 20 73 74 72 | 75 63 74 20 70 61 72 74 |mal, str|uct part|
|00000c40| 69 74 69 6f 6e 20 2a 70 | 61 72 74 29 3b 0d 73 74 |ition *p|art);.st|
|00000c50| 61 74 69 63 20 76 6f 69 | 64 20 09 09 09 09 09 09 |atic voi|d ......|
|00000c60| 64 69 73 63 61 72 64 5f | 63 6f 6e 66 75 73 69 6e |discard_|confusin|
|00000c70| 67 5f 6c 69 6e 65 73 20 | 28 72 65 67 69 73 74 65 |g_lines |(registe|
|00000c80| 72 20 73 74 72 75 63 74 | 20 66 69 6c 65 5f 64 61 |r struct| file_da|
|00000c90| 74 61 20 2a 66 69 6c 65 | 30 50 74 72 2c 0d 09 09 |ta *file|0Ptr,...|
|00000ca0| 09 09 09 09 09 09 09 09 | 09 09 09 09 09 09 09 09 |........|........|
|00000cb0| 09 09 09 09 09 09 20 72 | 65 67 69 73 74 65 72 20 |...... r|egister |
|00000cc0| 73 74 72 75 63 74 20 66 | 69 6c 65 5f 64 61 74 61 |struct f|ile_data|
|00000cd0| 20 2a 66 69 6c 65 31 50 | 74 72 29 3b 0d 73 74 61 | *file1P|tr);.sta|
|00000ce0| 74 69 63 20 76 6f 69 64 | 20 09 09 09 09 09 09 73 |tic void| ......s|
|00000cf0| 68 69 66 74 5f 62 6f 75 | 6e 64 61 72 69 65 73 20 |hift_bou|ndaries |
|00000d00| 28 73 74 72 75 63 74 20 | 66 69 6c 65 5f 64 61 74 |(struct |file_dat|
|00000d10| 61 20 2a 66 69 6c 65 30 | 50 74 72 2c 20 73 74 72 |a *file0|Ptr, str|
|00000d20| 75 63 74 20 66 69 6c 65 | 5f 64 61 74 61 20 2a 66 |uct file|_data *f|
|00000d30| 69 6c 65 31 50 74 72 29 | 3b 0d 0d 2f 2a 20 43 6f |ile1Ptr)|;../* Co|
|00000d40| 6e 73 20 61 6e 20 61 64 | 64 69 74 69 6f 6e 61 6c |ns an ad|ditional|
|00000d50| 20 65 6e 74 72 79 20 6f | 6e 74 6f 20 74 68 65 20 | entry o|nto the |
|00000d60| 66 72 6f 6e 74 20 6f 66 | 20 61 6e 20 65 64 69 74 |front of| an edit|
|00000d70| 20 73 63 72 69 70 74 20 | 4f 4c 44 2e 0d 09 20 4c | script |OLD... L|
|00000d80| 49 4e 45 30 20 61 6e 64 | 20 4c 49 4e 45 31 20 61 |INE0 and| LINE1 a|
|00000d90| 72 65 20 74 68 65 20 66 | 69 72 73 74 20 61 66 66 |re the f|irst aff|
|00000da0| 65 63 74 65 64 20 6c 69 | 6e 65 73 20 69 6e 20 74 |ected li|nes in t|
|00000db0| 68 65 20 74 77 6f 20 66 | 69 6c 65 73 20 28 6f 72 |he two f|iles (or|
|00000dc0| 69 67 69 6e 20 30 29 2e | 0d 09 20 44 45 4c 45 54 |igin 0).|.. DELET|
|00000dd0| 45 44 20 69 73 20 74 68 | 65 20 6e 75 6d 62 65 72 |ED is th|e number|
|00000de0| 20 6f 66 20 6c 69 6e 65 | 73 20 64 65 6c 65 74 65 | of line|s delete|
|00000df0| 64 20 68 65 72 65 20 66 | 72 6f 6d 20 66 69 6c 65 |d here f|rom file|
|00000e00| 20 30 2e 0d 09 20 49 4e | 53 45 52 54 45 44 20 69 | 0... IN|SERTED i|
|00000e10| 73 20 74 68 65 20 6e 75 | 6d 62 65 72 20 6f 66 20 |s the nu|mber of |
|00000e20| 6c 69 6e 65 73 20 69 6e | 73 65 72 74 65 64 20 68 |lines in|serted h|
|00000e30| 65 72 65 20 69 6e 20 66 | 69 6c 65 20 31 2e 0d 0d |ere in f|ile 1...|
|00000e40| 09 20 49 66 20 44 45 4c | 45 54 45 44 20 69 73 20 |. If DEL|ETED is |
|00000e50| 30 20 74 68 65 6e 20 4c | 49 4e 45 30 20 69 73 20 |0 then L|INE0 is |
|00000e60| 74 68 65 20 6e 75 6d 62 | 65 72 20 6f 66 20 74 68 |the numb|er of th|
|00000e70| 65 20 6c 69 6e 65 20 62 | 65 66 6f 72 65 0d 09 20 |e line b|efore.. |
|00000e80| 77 68 69 63 68 20 74 68 | 65 20 69 6e 73 65 72 74 |which th|e insert|
|00000e90| 69 6f 6e 20 77 61 73 20 | 64 6f 6e 65 3b 20 76 69 |ion was |done; vi|
|00000ea0| 63 65 20 76 65 72 73 61 | 20 66 6f 72 20 49 4e 53 |ce versa| for INS|
|00000eb0| 45 52 54 45 44 20 61 6e | 64 20 4c 49 4e 45 31 2e |ERTED an|d LINE1.|
|00000ec0| 20 20 2a 2f 0d 0d 73 74 | 61 74 69 63 20 73 74 72 |  */..st|atic str|
|00000ed0| 75 63 74 20 63 68 61 6e | 67 65 20 2a 0d 61 64 64 |uct chan|ge *.add|
|00000ee0| 5f 63 68 61 6e 67 65 20 | 28 69 6e 74 20 6c 69 6e |_change |(int lin|
|00000ef0| 65 30 2c 20 69 6e 74 20 | 6c 69 6e 65 31 2c 20 69 |e0, int |line1, i|
|00000f00| 6e 74 20 64 65 6c 65 74 | 65 64 2c 20 69 6e 74 20 |nt delet|ed, int |
|00000f10| 69 6e 73 65 72 74 65 64 | 2c 20 73 74 72 75 63 74 |inserted|, struct|
|00000f20| 20 63 68 61 6e 67 65 20 | 2a 6f 6c 64 29 0d 7b 0d | change |*old).{.|
|00000f30| 09 73 74 72 75 63 74 20 | 63 68 61 6e 67 65 20 2a |.struct |change *|
|00000f40| 6e 65 77 20 3d 20 28 73 | 74 72 75 63 74 20 63 68 |new = (s|truct ch|
|00000f50| 61 6e 67 65 20 2a 29 20 | 78 6d 61 6c 6c 6f 63 20 |ange *) |xmalloc |
|00000f60| 28 73 69 7a 65 6f 66 20 | 28 73 74 72 75 63 74 20 |(sizeof |(struct |
|00000f70| 63 68 61 6e 67 65 29 29 | 3b 0d 0d 09 6e 65 77 2d |change))|;...new-|
|00000f80| 3e 6c 69 6e 65 30 20 3d | 20 6c 69 6e 65 30 3b 0d |>line0 =| line0;.|
|00000f90| 09 6e 65 77 2d 3e 6c 69 | 6e 65 31 20 3d 20 6c 69 |.new->li|ne1 = li|
|00000fa0| 6e 65 31 3b 0d 09 6e 65 | 77 2d 3e 69 6e 73 65 72 |ne1;..ne|w->inser|
|00000fb0| 74 65 64 20 3d 20 69 6e | 73 65 72 74 65 64 3b 0d |ted = in|serted;.|
|00000fc0| 09 6e 65 77 2d 3e 64 65 | 6c 65 74 65 64 20 3d 20 |.new->de|leted = |
|00000fd0| 64 65 6c 65 74 65 64 3b | 0d 09 6e 65 77 2d 3e 6c |deleted;|..new->l|
|00000fe0| 69 6e 6b 20 3d 20 6f 6c | 64 3b 0d 09 72 65 74 75 |ink = ol|d;..retu|
|00000ff0| 72 6e 20 6e 65 77 3b 0d | 7d 0d 0d 2f 2a 20 53 63 |rn new;.|}../* Sc|
|00001000| 61 6e 20 74 68 65 20 74 | 61 62 6c 65 73 20 6f 66 |an the t|ables of|
|00001010| 20 77 68 69 63 68 20 6c | 69 6e 65 73 20 61 72 65 | which l|ines are|
|00001020| 20 69 6e 73 65 72 74 65 | 64 20 61 6e 64 20 64 65 | inserte|d and de|
|00001030| 6c 65 74 65 64 2c 0d 09 | 20 70 72 6f 64 75 63 69 |leted,..| produci|
|00001040| 6e 67 20 61 6e 20 65 64 | 69 74 20 73 63 72 69 70 |ng an ed|it scrip|
|00001050| 74 20 69 6e 20 66 6f 72 | 77 61 72 64 20 6f 72 64 |t in for|ward ord|
|00001060| 65 72 2e 20 20 2a 2f 0d | 0d 73 74 61 74 69 63 20 |er.  */.|.static |
|00001070| 73 74 72 75 63 74 20 63 | 68 61 6e 67 65 20 2a 0d |struct c|hange *.|
|00001080| 62 75 69 6c 64 5f 73 63 | 72 69 70 74 20 28 73 74 |build_sc|ript (st|
|00001090| 72 75 63 74 20 66 69 6c | 65 5f 64 61 74 61 20 2a |ruct fil|e_data *|
|000010a0| 66 69 6c 65 30 50 74 72 | 2c 20 73 74 72 75 63 74 |file0Ptr|, struct|
|000010b0| 20 66 69 6c 65 5f 64 61 | 74 61 20 2a 66 69 6c 65 | file_da|ta *file|
|000010c0| 31 50 74 72 29 0d 7b 0d | 09 73 74 72 75 63 74 20 |1Ptr).{.|.struct |
|000010d0| 63 68 61 6e 67 65 20 2a | 73 63 72 69 70 74 20 3d |change *|script =|
|000010e0| 20 30 3b 0d 09 63 68 61 | 72 20 2a 63 68 61 6e 67 | 0;..cha|r *chang|
|000010f0| 65 64 30 20 3d 20 66 69 | 6c 65 30 50 74 72 2d 3e |ed0 = fi|le0Ptr->|
|00001100| 63 68 61 6e 67 65 64 5f | 66 6c 61 67 3b 0d 09 63 |changed_|flag;..c|
|00001110| 68 61 72 20 2a 63 68 61 | 6e 67 65 64 31 20 3d 20 |har *cha|nged1 = |
|00001120| 66 69 6c 65 31 50 74 72 | 2d 3e 63 68 61 6e 67 65 |file1Ptr|->change|
|00001130| 64 5f 66 6c 61 67 3b 0d | 09 69 6e 74 20 6c 65 6e |d_flag;.|.int len|
|00001140| 30 20 3d 20 66 69 6c 65 | 30 50 74 72 2d 3e 62 75 |0 = file|0Ptr->bu|
|00001150| 66 66 65 72 65 64 5f 6c | 69 6e 65 73 3b 0d 09 69 |ffered_l|ines;..i|
|00001160| 6e 74 20 6c 65 6e 31 20 | 3d 20 66 69 6c 65 31 50 |nt len1 |= file1P|
|00001170| 74 72 2d 3e 62 75 66 66 | 65 72 65 64 5f 6c 69 6e |tr->buff|ered_lin|
|00001180| 65 73 3b 0d 09 69 6e 74 | 20 69 30 20 3d 20 6c 65 |es;..int| i0 = le|
|00001190| 6e 30 2c 20 69 31 20 3d | 20 6c 65 6e 31 3b 0d 0d |n0, i1 =| len1;..|
|000011a0| 09 2f 2a 20 4e 6f 74 65 | 20 74 68 61 74 20 63 68 |./* Note| that ch|
|000011b0| 61 6e 67 65 64 4e 5b 2d | 31 5d 20 64 6f 65 73 20 |angedN[-|1] does |
|000011c0| 65 78 69 73 74 2c 20 61 | 6e 64 20 63 6f 6e 74 61 |exist, a|nd conta|
|000011d0| 69 6e 73 20 30 2e 20 20 | 2a 2f 0d 0d 09 77 68 69 |ins 0.  |*/...whi|
|000011e0| 6c 65 20 28 69 30 20 3e | 3d 20 30 20 7c 7c 20 69 |le (i0 >|= 0 || i|
|000011f0| 31 20 3e 3d 20 30 29 0d | 09 09 7b 0d 09 09 09 69 |1 >= 0).|..{....i|
|00001200| 66 20 28 63 68 61 6e 67 | 65 64 30 5b 69 30 20 2d |f (chang|ed0[i0 -|
|00001210| 20 31 5d 20 7c 7c 20 63 | 68 61 6e 67 65 64 31 5b | 1] || c|hanged1[|
|00001220| 69 31 20 2d 20 31 5d 29 | 0d 09 09 09 09 7b 0d 09 |i1 - 1])|.....{..|
|00001230| 09 09 09 09 69 6e 74 20 | 6c 69 6e 65 30 20 3d 20 |....int |line0 = |
|00001240| 69 30 2c 20 6c 69 6e 65 | 31 20 3d 20 69 31 3b 0d |i0, line|1 = i1;.|
|00001250| 0d 09 09 09 09 09 2f 2a | 20 46 69 6e 64 20 23 20 |....../*| Find # |
|00001260| 6c 69 6e 65 73 20 63 68 | 61 6e 67 65 64 20 68 65 |lines ch|anged he|
|00001270| 72 65 20 69 6e 20 65 61 | 63 68 20 66 69 6c 65 2e |re in ea|ch file.|
|00001280| 09 2a 2f 0d 09 09 09 09 | 09 77 68 69 6c 65 20 28 |.*/.....|.while (|
|00001290| 63 68 61 6e 67 65 64 30 | 5b 69 30 20 2d 20 31 5d |changed0|[i0 - 1]|
|000012a0| 29 20 2d 2d 69 30 3b 0d | 09 09 09 09 09 77 68 69 |) --i0;.|.....whi|
|000012b0| 6c 65 20 28 63 68 61 6e | 67 65 64 31 5b 69 31 20 |le (chan|ged1[i1 |
|000012c0| 2d 20 31 5d 29 20 2d 2d | 69 31 3b 0d 0d 09 09 09 |- 1]) --|i1;.....|
|000012d0| 09 09 2f 2a 20 52 65 63 | 6f 72 64 20 74 68 69 73 |../* Rec|ord this|
|000012e0| 20 63 68 61 6e 67 65 2e | 09 2a 2f 0d 09 09 09 09 | change.|.*/.....|
|000012f0| 09 73 63 72 69 70 74 20 | 3d 20 61 64 64 5f 63 68 |.script |= add_ch|
|00001300| 61 6e 67 65 20 28 69 30 | 2c 20 69 31 2c 20 6c 69 |ange (i0|, i1, li|
|00001310| 6e 65 30 20 2d 20 69 30 | 2c 20 6c 69 6e 65 31 20 |ne0 - i0|, line1 |
|00001320| 2d 20 69 31 2c 20 73 63 | 72 69 70 74 29 3b 0d 09 |- i1, sc|ript);..|
|00001330| 09 09 09 7d 0d 0d 09 09 | 09 2f 2a 20 57 65 20 68 |...}....|./* We h|
|00001340| 61 76 65 20 72 65 61 63 | 68 65 64 20 6c 69 6e 65 |ave reac|hed line|
|00001350| 73 20 69 6e 20 74 68 65 | 20 74 77 6f 20 66 69 6c |s in the| two fil|
|00001360| 65 73 20 74 68 61 74 20 | 6d 61 74 63 68 20 65 61 |es that |match ea|
|00001370| 63 68 20 6f 74 68 65 72 | 2e 09 2a 2f 0d 09 09 09 |ch other|..*/....|
|00001380| 69 30 2d 2d 2c 20 69 31 | 2d 2d 3b 0d 09 09 7d 0d |i0--, i1|--;...}.|
|00001390| 0d 09 72 65 74 75 72 6e | 20 73 63 72 69 70 74 3b |..return| script;|
|000013a0| 0d 7d 0d 0d 2f 2a 20 43 | 6f 6d 70 61 72 65 20 69 |.}../* C|ompare i|
|000013b0| 6e 20 64 65 74 61 69 6c | 20 63 6f 6e 74 69 67 75 |n detail| contigu|
|000013c0| 6f 75 73 20 73 75 62 73 | 65 71 75 65 6e 63 65 73 |ous subs|equences|
|000013d0| 20 6f 66 20 74 68 65 20 | 74 77 6f 20 66 69 6c 65 | of the |two file|
|000013e0| 73 0d 20 20 20 77 68 69 | 63 68 20 61 72 65 20 6b |s.   whi|ch are k|
|000013f0| 6e 6f 77 6e 2c 20 61 73 | 20 61 20 77 68 6f 6c 65 |nown, as| a whole|
|00001400| 2c 20 74 6f 20 6d 61 74 | 63 68 20 65 61 63 68 20 |, to mat|ch each |
|00001410| 6f 74 68 65 72 2e 0d 0d | 20 20 20 54 68 65 20 72 |other...|   The r|
|00001420| 65 73 75 6c 74 73 20 61 | 72 65 20 72 65 63 6f 72 |esults a|re recor|
|00001430| 64 65 64 20 69 6e 20 74 | 68 65 20 76 65 63 74 6f |ded in t|he vecto|
|00001440| 72 73 20 66 69 6c 65 73 | 5b 4e 5d 2e 63 68 61 6e |rs files|[N].chan|
|00001450| 67 65 64 5f 66 6c 61 67 | 2c 20 62 79 0d 20 20 20 |ged_flag|, by.   |
|00001460| 73 74 6f 72 69 6e 67 20 | 61 20 31 20 69 6e 20 74 |storing |a 1 in t|
|00001470| 68 65 20 65 6c 65 6d 65 | 6e 74 20 66 6f 72 20 65 |he eleme|nt for e|
|00001480| 61 63 68 20 6c 69 6e 65 | 20 74 68 61 74 20 69 73 |ach line| that is|
|00001490| 20 61 6e 20 69 6e 73 65 | 72 74 69 6f 6e 20 6f 72 | an inse|rtion or|
|000014a0| 20 64 65 6c 65 74 69 6f | 6e 2e 0d 0d 20 20 20 54 | deletio|n...   T|
|000014b0| 68 65 20 73 75 62 73 65 | 71 75 65 6e 63 65 20 6f |he subse|quence o|
|000014c0| 66 20 66 69 6c 65 20 30 | 20 69 73 20 5b 58 4f 46 |f file 0| is [XOF|
|000014d0| 46 2c 20 58 4c 49 4d 29 | 20 61 6e 64 20 6c 69 6b |F, XLIM)| and lik|
|000014e0| 65 77 69 73 65 20 66 6f | 72 20 66 69 6c 65 20 31 |ewise fo|r file 1|
|000014f0| 2e 0d 0d 20 20 20 4e 6f | 74 65 20 74 68 61 74 20 |...   No|te that |
|00001500| 58 4c 49 4d 2c 20 59 4c | 49 4d 20 61 72 65 20 65 |XLIM, YL|IM are e|
|00001510| 78 63 6c 75 73 69 76 65 | 20 62 6f 75 6e 64 73 2e |xclusive| bounds.|
|00001520| 0d 20 20 20 41 6c 6c 20 | 6c 69 6e 65 20 6e 75 6d |.   All |line num|
|00001530| 62 65 72 73 20 61 72 65 | 20 6f 72 69 67 69 6e 2d |bers are| origin-|
|00001540| 30 20 61 6e 64 20 64 69 | 73 63 61 72 64 65 64 20 |0 and di|scarded |
|00001550| 6c 69 6e 65 73 20 61 72 | 65 20 6e 6f 74 20 63 6f |lines ar|e not co|
|00001560| 75 6e 74 65 64 2e 0d 20 | 0d 20 20 20 49 66 20 4d |unted.. |.   If M|
|00001570| 49 4e 49 4d 41 4c 20 69 | 73 20 6e 6f 6e 7a 65 72 |INIMAL i|s nonzer|
|00001580| 6f 2c 20 66 69 6e 64 20 | 61 20 6d 69 6e 69 6d 61 |o, find |a minima|
|00001590| 6c 20 64 69 66 66 65 72 | 65 6e 63 65 20 6e 6f 20 |l differ|ence no |
|000015a0| 6d 61 74 74 65 72 20 68 | 6f 77 0d 20 20 20 65 78 |matter h|ow.   ex|
|000015b0| 70 65 6e 73 69 76 65 20 | 69 74 20 69 73 2e 20 20 |pensive |it is.  |
|000015c0| 2a 2f 0d 0d 73 74 61 74 | 69 63 20 76 6f 69 64 0d |*/..stat|ic void.|
|000015d0| 63 6f 6d 70 61 72 65 73 | 65 71 20 28 73 74 72 75 |compares|eq (stru|
|000015e0| 63 74 20 66 69 6c 65 5f | 64 61 74 61 20 2a 66 69 |ct file_|data *fi|
|000015f0| 6c 65 30 50 74 72 2c 20 | 73 74 72 75 63 74 20 66 |le0Ptr, |struct f|
|00001600| 69 6c 65 5f 64 61 74 61 | 20 2a 66 69 6c 65 31 50 |ile_data| *file1P|
|00001610| 74 72 2c 0d 09 09 09 09 | 09 09 69 6e 74 20 78 6f |tr,.....|..int xo|
|00001620| 66 66 2c 20 69 6e 74 20 | 78 6c 69 6d 2c 20 69 6e |ff, int |xlim, in|
|00001630| 74 20 79 6f 66 66 2c 20 | 69 6e 74 20 79 6c 69 6d |t yoff, |int ylim|
|00001640| 2c 20 69 6e 74 20 6d 69 | 6e 69 6d 61 6c 29 0d 7b |, int mi|nimal).{|
|00001650| 0d 20 20 69 6e 74 20 2a | 20 63 6f 6e 73 74 20 78 |.  int *| const x|
|00001660| 76 20 3d 20 78 76 65 63 | 3b 20 2f 2a 20 48 65 6c |v = xvec|; /* Hel|
|00001670| 70 20 74 68 65 20 63 6f | 6d 70 69 6c 65 72 2e 20 |p the co|mpiler. |
|00001680| 20 2a 2f 0d 20 20 69 6e | 74 20 2a 20 63 6f 6e 73 | */.  in|t * cons|
|00001690| 74 20 79 76 20 3d 20 79 | 76 65 63 3b 0d 0d 09 2f |t yv = y|vec;.../|
|000016a0| 2a 20 53 6c 69 64 65 20 | 64 6f 77 6e 20 74 68 65 |* Slide |down the|
|000016b0| 20 62 6f 74 74 6f 6d 20 | 69 6e 69 74 69 61 6c 20 | bottom |initial |
|000016c0| 64 69 61 67 6f 6e 61 6c | 2e 20 2a 2f 0d 09 77 68 |diagonal|. */..wh|
|000016d0| 69 6c 65 20 28 78 6f 66 | 66 20 3c 20 78 6c 69 6d |ile (xof|f < xlim|
|000016e0| 20 26 26 20 79 6f 66 66 | 20 3c 20 79 6c 69 6d 20 | && yoff| < ylim |
|000016f0| 26 26 20 78 76 5b 78 6f | 66 66 5d 20 3d 3d 20 79 |&& xv[xo|ff] == y|
|00001700| 76 5b 79 6f 66 66 5d 29 | 0d 09 09 2b 2b 78 6f 66 |v[yoff])|...++xof|
|00001710| 66 2c 20 2b 2b 79 6f 66 | 66 3b 0d 09 2f 2a 20 53 |f, ++yof|f;../* S|
|00001720| 6c 69 64 65 20 75 70 20 | 74 68 65 20 74 6f 70 20 |lide up |the top |
|00001730| 69 6e 69 74 69 61 6c 20 | 64 69 61 67 6f 6e 61 6c |initial |diagonal|
|00001740| 2e 20 2a 2f 0d 09 77 68 | 69 6c 65 20 28 78 6c 69 |. */..wh|ile (xli|
|00001750| 6d 20 3e 20 78 6f 66 66 | 20 26 26 20 79 6c 69 6d |m > xoff| && ylim|
|00001760| 20 3e 20 79 6f 66 66 20 | 26 26 20 78 76 5b 78 6c | > yoff |&& xv[xl|
|00001770| 69 6d 20 2d 20 31 5d 20 | 3d 3d 20 79 76 5b 79 6c |im - 1] |== yv[yl|
|00001780| 69 6d 20 2d 20 31 5d 29 | 0d 09 09 2d 2d 78 6c 69 |im - 1])|...--xli|
|00001790| 6d 2c 20 2d 2d 79 6c 69 | 6d 3b 0d 09 0d 09 2f 2a |m, --yli|m;..../*|
|000017a0| 20 48 61 6e 64 6c 65 20 | 73 69 6d 70 6c 65 20 63 | Handle |simple c|
|000017b0| 61 73 65 73 2e 20 2a 2f | 0d 09 69 66 20 28 78 6f |ases. */|..if (xo|
|000017c0| 66 66 20 3d 3d 20 78 6c | 69 6d 29 0d 09 09 77 68 |ff == xl|im)...wh|
|000017d0| 69 6c 65 20 28 79 6f 66 | 66 20 3c 20 79 6c 69 6d |ile (yof|f < ylim|
|000017e0| 29 0d 09 09 09 66 69 6c | 65 31 50 74 72 2d 3e 63 |)....fil|e1Ptr->c|
|000017f0| 68 61 6e 67 65 64 5f 66 | 6c 61 67 5b 66 69 6c 65 |hanged_f|lag[file|
|00001800| 31 50 74 72 2d 3e 72 65 | 61 6c 69 6e 64 65 78 65 |1Ptr->re|alindexe|
|00001810| 73 5b 79 6f 66 66 2b 2b | 5d 5d 20 3d 20 31 3b 0d |s[yoff++|]] = 1;.|
|00001820| 09 65 6c 73 65 20 69 66 | 20 28 79 6f 66 66 20 3d |.else if| (yoff =|
|00001830| 3d 20 79 6c 69 6d 29 0d | 09 09 77 68 69 6c 65 20 |= ylim).|..while |
|00001840| 28 78 6f 66 66 20 3c 20 | 78 6c 69 6d 29 0d 09 09 |(xoff < |xlim)...|
|00001850| 09 66 69 6c 65 30 50 74 | 72 2d 3e 63 68 61 6e 67 |.file0Pt|r->chang|
|00001860| 65 64 5f 66 6c 61 67 5b | 66 69 6c 65 30 50 74 72 |ed_flag[|file0Ptr|
|00001870| 2d 3e 72 65 61 6c 69 6e | 64 65 78 65 73 5b 78 6f |->realin|dexes[xo|
|00001880| 66 66 2b 2b 5d 5d 20 3d | 20 31 3b 0d 09 65 6c 73 |ff++]] =| 1;..els|
|00001890| 65 0d 09 09 7b 0d 09 09 | 09 69 6e 74 20 63 3b 0d |e...{...|.int c;.|
|000018a0| 09 09 09 73 74 72 75 63 | 74 20 70 61 72 74 69 74 |...struc|t partit|
|000018b0| 69 6f 6e 20 70 61 72 74 | 3b 0d 0d 09 09 09 2f 2a |ion part|;...../*|
|000018c0| 20 46 69 6e 64 20 61 20 | 70 6f 69 6e 74 20 6f 66 | Find a |point of|
|000018d0| 20 63 6f 72 72 65 73 70 | 6f 6e 64 65 6e 63 65 20 | corresp|ondence |
|000018e0| 69 6e 20 74 68 65 20 6d | 69 64 64 6c 65 20 6f 66 |in the m|iddle of|
|000018f0| 20 74 68 65 20 66 69 6c | 65 73 2e 20 20 2a 2f 0d | the fil|es.  */.|
|00001900| 0d 09 09 09 63 20 3d 20 | 64 69 61 67 20 28 78 6f |....c = |diag (xo|
|00001910| 66 66 2c 20 78 6c 69 6d | 2c 20 79 6f 66 66 2c 20 |ff, xlim|, yoff, |
|00001920| 79 6c 69 6d 2c 20 6d 69 | 6e 69 6d 61 6c 2c 20 26 |ylim, mi|nimal, &|
|00001930| 70 61 72 74 29 3b 0d 0d | 09 09 09 69 66 20 28 63 |part);..|...if (c|
|00001940| 20 3d 3d 20 31 29 0d 09 | 09 09 09 7b 0d 09 09 09 | == 1)..|...{....|
|00001950| 09 09 2f 2a 20 54 68 69 | 73 20 73 68 6f 75 6c 64 |../* Thi|s should|
|00001960| 20 62 65 20 69 6d 70 6f | 73 73 69 62 6c 65 2c 20 | be impo|ssible, |
|00001970| 62 65 63 61 75 73 65 20 | 69 74 20 69 6d 70 6c 69 |because |it impli|
|00001980| 65 73 20 74 68 61 74 0d | 09 09 09 09 09 09 20 6f |es that.|...... o|
|00001990| 6e 65 20 6f 66 20 74 68 | 65 20 74 77 6f 20 73 75 |ne of th|e two su|
|000019a0| 62 73 65 71 75 65 6e 63 | 65 73 20 69 73 20 65 6d |bsequenc|es is em|
|000019b0| 70 74 79 2c 0d 09 09 09 | 09 09 09 20 61 6e 64 20 |pty,....|... and |
|000019c0| 74 68 61 74 20 63 61 73 | 65 20 77 61 73 20 68 61 |that cas|e was ha|
|000019d0| 6e 64 6c 65 64 20 61 62 | 6f 76 65 20 77 69 74 68 |ndled ab|ove with|
|000019e0| 6f 75 74 20 63 61 6c 6c | 69 6e 67 20 60 64 69 61 |out call|ing `dia|
|000019f0| 67 27 2e 0d 09 09 09 09 | 09 09 20 4c 65 74 27 73 |g'......|.. Let's|
|00001a00| 20 76 65 72 69 66 79 20 | 74 68 61 74 20 74 68 69 | verify |that thi|
|00001a10| 73 20 69 73 20 74 72 75 | 65 2e 20 20 2a 2f 0d 09 |s is tru|e.  */..|
|00001a20| 09 09 09 09 61 62 6f 72 | 74 20 28 29 3b 0d 23 69 |....abor|t ();.#i|
|00001a30| 66 20 30 0d 09 09 09 09 | 09 2f 2a 20 54 68 65 20 |f 0.....|./* The |
|00001a40| 74 77 6f 20 73 75 62 73 | 65 71 75 65 6e 63 65 73 |two subs|equences|
|00001a50| 20 64 69 66 66 65 72 20 | 62 79 20 61 20 73 69 6e | differ |by a sin|
|00001a60| 67 6c 65 20 69 6e 73 65 | 72 74 20 6f 72 20 64 65 |gle inse|rt or de|
|00001a70| 6c 65 74 65 3b 0d 09 09 | 09 09 09 09 20 72 65 63 |lete;...|.... rec|
|00001a80| 6f 72 64 20 69 74 20 61 | 6e 64 20 77 65 20 61 72 |ord it a|nd we ar|
|00001a90| 65 20 64 6f 6e 65 2e 20 | 20 2a 2f 0d 09 09 09 09 |e done. | */.....|
|00001aa0| 09 69 66 20 28 70 61 72 | 74 2e 78 6d 69 64 20 2d |.if (par|t.xmid -|
|00001ab0| 20 70 61 72 74 2e 79 6d | 69 64 20 3c 20 78 6f 66 | part.ym|id < xof|
|00001ac0| 66 20 2d 20 79 6f 66 66 | 29 0d 09 09 09 09 09 09 |f - yoff|).......|
|00001ad0| 66 69 6c 65 73 5b 31 5d | 2e 63 68 61 6e 67 65 64 |files[1]|.changed|
|00001ae0| 5f 66 6c 61 67 5b 66 69 | 6c 65 73 5b 31 5d 2e 72 |_flag[fi|les[1].r|
|00001af0| 65 61 6c 69 6e 64 65 78 | 65 73 5b 70 61 72 74 2e |ealindex|es[part.|
|00001b00| 79 6d 69 64 20 2d 20 31 | 5d 5d 20 3d 20 31 3b 0d |ymid - 1|]] = 1;.|
|00001b10| 09 09 09 09 09 65 6c 73 | 65 0d 09 09 09 09 09 09 |.....els|e.......|
|00001b20| 66 69 6c 65 73 5b 30 5d | 2e 63 68 61 6e 67 65 64 |files[0]|.changed|
|00001b30| 5f 66 6c 61 67 5b 66 69 | 6c 65 73 5b 30 5d 2e 72 |_flag[fi|les[0].r|
|00001b40| 65 61 6c 69 6e 64 65 78 | 65 73 5b 70 61 72 74 2e |ealindex|es[part.|
|00001b50| 78 6d 69 64 5d 5d 20 3d | 20 31 3b 0d 23 65 6e 64 |xmid]] =| 1;.#end|
|00001b60| 69 66 0d 09 09 09 09 7d | 0d 20 20 20 20 20 20 65 |if.....}|.      e|
|00001b70| 6c 73 65 0d 09 09 09 09 | 7b 0d 09 09 09 09 09 2f |lse.....|{....../|
|00001b80| 2a 20 55 73 65 20 74 68 | 65 20 70 61 72 74 69 74 |* Use th|e partit|
|00001b90| 69 6f 6e 73 20 74 6f 20 | 73 70 6c 69 74 20 74 68 |ions to |split th|
|00001ba0| 69 73 20 70 72 6f 62 6c | 65 6d 20 69 6e 74 6f 20 |is probl|em into |
|00001bb0| 73 75 62 70 72 6f 62 6c | 65 6d 73 2e 20 20 2a 2f |subprobl|ems.  */|
|00001bc0| 0d 09 09 09 09 09 63 6f | 6d 70 61 72 65 73 65 71 |......co|mpareseq|
|00001bd0| 20 28 66 69 6c 65 30 50 | 74 72 2c 20 66 69 6c 65 | (file0P|tr, file|
|00001be0| 31 50 74 72 2c 20 78 6f | 66 66 2c 20 70 61 72 74 |1Ptr, xo|ff, part|
|00001bf0| 2e 78 6d 69 64 2c 20 79 | 6f 66 66 2c 20 70 61 72 |.xmid, y|off, par|
|00001c00| 74 2e 79 6d 69 64 2c 20 | 70 61 72 74 2e 6c 6f 5f |t.ymid, |part.lo_|
|00001c10| 6d 69 6e 69 6d 61 6c 29 | 3b 0d 09 09 09 09 09 63 |minimal)|;......c|
|00001c20| 6f 6d 70 61 72 65 73 65 | 71 20 28 66 69 6c 65 30 |omparese|q (file0|
|00001c30| 50 74 72 2c 20 66 69 6c | 65 31 50 74 72 2c 20 70 |Ptr, fil|e1Ptr, p|
|00001c40| 61 72 74 2e 78 6d 69 64 | 2c 20 78 6c 69 6d 2c 20 |art.xmid|, xlim, |
|00001c50| 70 61 72 74 2e 79 6d 69 | 64 2c 20 79 6c 69 6d 2c |part.ymi|d, ylim,|
|00001c60| 20 70 61 72 74 2e 68 69 | 5f 6d 69 6e 69 6d 61 6c | part.hi|_minimal|
|00001c70| 29 3b 0d 09 09 09 09 7d | 0d 09 09 7d 0d 7d 0d 0d |);.....}|...}.}..|
|00001c80| 2f 2a 20 46 69 6e 64 20 | 74 68 65 20 6d 69 64 70 |/* Find |the midp|
|00001c90| 6f 69 6e 74 20 6f 66 20 | 74 68 65 20 73 68 6f 72 |oint of |the shor|
|00001ca0| 74 65 73 74 20 65 64 69 | 74 20 73 63 72 69 70 74 |test edi|t script|
|00001cb0| 20 66 6f 72 20 61 20 73 | 70 65 63 69 66 69 65 64 | for a s|pecified|
|00001cc0| 0d 20 20 20 70 6f 72 74 | 69 6f 6e 20 6f 66 20 74 |.   port|ion of t|
|00001cd0| 68 65 20 74 77 6f 20 66 | 69 6c 65 73 2e 0d 0d 20 |he two f|iles... |
|00001ce0| 20 20 53 63 61 6e 20 66 | 72 6f 6d 20 74 68 65 20 |  Scan f|rom the |
|00001cf0| 62 65 67 69 6e 6e 69 6e | 67 73 20 6f 66 20 74 68 |beginnin|gs of th|
|00001d00| 65 20 66 69 6c 65 73 2c | 20 61 6e 64 20 73 69 6d |e files,| and sim|
|00001d10| 75 6c 74 61 6e 65 6f 75 | 73 6c 79 20 66 72 6f 6d |ultaneou|sly from|
|00001d20| 20 74 68 65 20 65 6e 64 | 73 2c 0d 20 20 20 64 6f | the end|s,.   do|
|00001d30| 69 6e 67 20 61 20 62 72 | 65 61 64 74 68 2d 66 69 |ing a br|eadth-fi|
|00001d40| 72 73 74 20 73 65 61 72 | 63 68 20 74 68 72 6f 75 |rst sear|ch throu|
|00001d50| 67 68 20 74 68 65 20 73 | 70 61 63 65 20 6f 66 20 |gh the s|pace of |
|00001d60| 65 64 69 74 2d 73 65 71 | 75 65 6e 63 65 2e 0d 20 |edit-seq|uence.. |
|00001d70| 20 20 57 68 65 6e 20 74 | 68 65 20 74 77 6f 20 73 |  When t|he two s|
|00001d80| 65 61 72 63 68 65 73 20 | 6d 65 65 74 2c 20 77 65 |earches |meet, we|
|00001d90| 20 68 61 76 65 20 66 6f | 75 6e 64 20 74 68 65 20 | have fo|und the |
|00001da0| 6d 69 64 70 6f 69 6e 74 | 20 6f 66 20 74 68 65 20 |midpoint| of the |
|00001db0| 73 68 6f 72 74 65 73 74 | 0d 20 20 20 65 64 69 74 |shortest|.   edit|
|00001dc0| 20 73 65 71 75 65 6e 63 | 65 2e 0d 0d 20 20 20 49 | sequenc|e...   I|
|00001dd0| 66 20 4d 49 4e 49 4d 41 | 4c 20 69 73 20 6e 6f 6e |f MINIMA|L is non|
|00001de0| 7a 65 72 6f 2c 20 66 69 | 6e 64 20 74 68 65 20 6d |zero, fi|nd the m|
|00001df0| 69 6e 69 6d 61 6c 20 65 | 64 69 74 20 73 63 72 69 |inimal e|dit scri|
|00001e00| 70 74 20 72 65 67 61 72 | 64 6c 65 73 73 0d 20 20 |pt regar|dless.  |
|00001e10| 20 6f 66 20 65 78 70 65 | 6e 73 65 2e 20 20 4f 74 | of expe|nse.  Ot|
|00001e20| 68 65 72 77 69 73 65 2c | 20 69 66 20 74 68 65 20 |herwise,| if the |
|00001e30| 73 65 61 72 63 68 20 69 | 73 20 74 6f 6f 20 65 78 |search i|s too ex|
|00001e40| 70 65 6e 73 69 76 65 2c | 20 75 73 65 0d 20 20 20 |pensive,| use.   |
|00001e50| 68 65 75 72 69 73 74 69 | 63 73 20 74 6f 20 73 74 |heuristi|cs to st|
|00001e60| 6f 70 20 74 68 65 20 73 | 65 61 72 63 68 20 61 6e |op the s|earch an|
|00001e70| 64 20 72 65 70 6f 72 74 | 20 61 20 73 75 62 6f 70 |d report| a subop|
|00001e80| 74 69 6d 61 6c 20 61 6e | 73 77 65 72 2e 0d 0d 20 |timal an|swer... |
|00001e90| 20 20 53 65 74 20 50 41 | 52 54 2d 3e 28 58 4d 49 |  Set PA|RT->(XMI|
|00001ea0| 44 2c 59 4d 49 44 29 20 | 74 6f 20 74 68 65 20 6d |D,YMID) |to the m|
|00001eb0| 69 64 70 6f 69 6e 74 20 | 28 58 4d 49 44 2c 59 4d |idpoint |(XMID,YM|
|00001ec0| 49 44 29 2e 20 20 54 68 | 65 20 64 69 61 67 6f 6e |ID).  Th|e diagon|
|00001ed0| 61 6c 20 6e 75 6d 62 65 | 72 0d 20 20 20 58 4d 49 |al numbe|r.   XMI|
|00001ee0| 44 20 2d 20 59 4d 49 44 | 20 65 71 75 61 6c 73 20 |D - YMID| equals |
|00001ef0| 74 68 65 20 6e 75 6d 62 | 65 72 20 6f 66 20 69 6e |the numb|er of in|
|00001f00| 73 65 72 74 65 64 20 6c | 69 6e 65 73 20 6d 69 6e |serted l|ines min|
|00001f10| 75 73 20 74 68 65 20 6e | 75 6d 62 65 72 0d 20 20 |us the n|umber.  |
|00001f20| 20 6f 66 20 64 65 6c 65 | 74 65 64 20 6c 69 6e 65 | of dele|ted line|
|00001f30| 73 20 28 63 6f 75 6e 74 | 69 6e 67 20 6f 6e 6c 79 |s (count|ing only|
|00001f40| 20 6c 69 6e 65 73 20 62 | 65 66 6f 72 65 20 74 68 | lines b|efore th|
|00001f50| 65 20 6d 69 64 70 6f 69 | 6e 74 29 2e 0d 20 20 20 |e midpoi|nt)..   |
|00001f60| 52 65 74 75 72 6e 20 74 | 68 65 20 61 70 70 72 6f |Return t|he appro|
|00001f70| 78 69 6d 61 74 65 20 65 | 64 69 74 20 63 6f 73 74 |ximate e|dit cost|
|00001f80| 3b 20 74 68 69 73 20 69 | 73 20 74 68 65 20 74 6f |; this i|s the to|
|00001f90| 74 61 6c 20 6e 75 6d 62 | 65 72 20 6f 66 0d 20 20 |tal numb|er of.  |
|00001fa0| 20 6c 69 6e 65 73 20 69 | 6e 73 65 72 74 65 64 20 | lines i|nserted |
|00001fb0| 6f 72 20 64 65 6c 65 74 | 65 64 20 28 63 6f 75 6e |or delet|ed (coun|
|00001fc0| 74 69 6e 67 20 6f 6e 6c | 79 20 6c 69 6e 65 73 20 |ting onl|y lines |
|00001fd0| 62 65 66 6f 72 65 20 74 | 68 65 20 6d 69 64 70 6f |before t|he midpo|
|00001fe0| 69 6e 74 29 2c 0d 20 20 | 20 75 6e 6c 65 73 73 20 |int),.  | unless |
|00001ff0| 61 20 68 65 75 72 69 73 | 74 69 63 20 69 73 20 75 |a heuris|tic is u|
|00002000| 73 65 64 20 74 6f 20 74 | 65 72 6d 69 6e 61 74 65 |sed to t|erminate|
|00002010| 20 74 68 65 20 73 65 61 | 72 63 68 20 70 72 65 6d | the sea|rch prem|
|00002020| 61 74 75 72 65 6c 79 2e | 0d 0d 20 20 20 53 65 74 |aturely.|..   Set|
|00002030| 20 50 41 52 54 2d 3e 4c | 45 46 54 5f 4d 49 4e 49 | PART->L|EFT_MINI|
|00002040| 4d 41 4c 20 74 6f 20 6e | 6f 6e 7a 65 72 6f 20 69 |MAL to n|onzero i|
|00002050| 66 66 20 74 68 65 20 6d | 69 6e 69 6d 61 6c 20 65 |ff the m|inimal e|
|00002060| 64 69 74 20 73 63 72 69 | 70 74 20 66 6f 72 20 74 |dit scri|pt for t|
|00002070| 68 65 0d 20 20 20 6c 65 | 66 74 20 68 61 6c 66 20 |he.   le|ft half |
|00002080| 6f 66 20 74 68 65 20 70 | 61 72 74 69 74 69 6f 6e |of the p|artition|
|00002090| 20 69 73 20 6b 6e 6f 77 | 6e 3b 20 73 69 6d 69 6c | is know|n; simil|
|000020a0| 61 72 6c 79 20 66 6f 72 | 20 50 41 52 54 2d 3e 52 |arly for| PART->R|
|000020b0| 49 47 48 54 5f 4d 49 4e | 49 4d 41 4c 2e 0d 0d 20 |IGHT_MIN|IMAL... |
|000020c0| 20 20 54 68 69 73 20 66 | 75 6e 63 74 69 6f 6e 20 |  This f|unction |
|000020d0| 61 73 73 75 6d 65 73 20 | 74 68 61 74 20 74 68 65 |assumes |that the|
|000020e0| 20 66 69 72 73 74 20 6c | 69 6e 65 73 20 6f 66 20 | first l|ines of |
|000020f0| 74 68 65 20 73 70 65 63 | 69 66 69 65 64 20 70 6f |the spec|ified po|
|00002100| 72 74 69 6f 6e 73 0d 20 | 20 20 6f 66 20 74 68 65 |rtions. |  of the|
|00002110| 20 74 77 6f 20 66 69 6c | 65 73 20 64 6f 20 6e 6f | two fil|es do no|
|00002120| 74 20 6d 61 74 63 68 2c | 20 61 6e 64 20 6c 69 6b |t match,| and lik|
|00002130| 65 77 69 73 65 20 74 68 | 61 74 20 74 68 65 20 6c |ewise th|at the l|
|00002140| 61 73 74 20 6c 69 6e 65 | 73 20 64 6f 20 6e 6f 74 |ast line|s do not|
|00002150| 0d 20 20 20 6d 61 74 63 | 68 2e 20 20 54 68 65 20 |.   matc|h.  The |
|00002160| 63 61 6c 6c 65 72 20 6d | 75 73 74 20 74 72 69 6d |caller m|ust trim|
|00002170| 20 6d 61 74 63 68 69 6e | 67 20 6c 69 6e 65 73 20 | matchin|g lines |
|00002180| 66 72 6f 6d 20 74 68 65 | 20 62 65 67 69 6e 6e 69 |from the| beginni|
|00002190| 6e 67 20 61 6e 64 20 65 | 6e 64 0d 20 20 20 6f 66 |ng and e|nd.   of|
|000021a0| 20 74 68 65 20 70 6f 72 | 74 69 6f 6e 73 20 69 74 | the por|tions it|
|000021b0| 20 69 73 20 67 6f 69 6e | 67 20 74 6f 20 73 70 65 | is goin|g to spe|
|000021c0| 63 69 66 79 2e 0d 0d 20 | 20 20 49 66 20 77 65 20 |cify... |  If we |
|000021d0| 72 65 74 75 72 6e 20 74 | 68 65 20 22 77 72 6f 6e |return t|he "wron|
|000021e0| 67 22 20 70 61 72 74 69 | 74 69 6f 6e 73 2c 0d 20 |g" parti|tions,. |
|000021f0| 20 20 74 68 65 20 77 6f | 72 73 74 20 74 68 69 73 |  the wo|rst this|
|00002200| 20 63 61 6e 20 64 6f 20 | 69 73 20 63 61 75 73 65 | can do |is cause|
|00002210| 20 73 75 62 6f 70 74 69 | 6d 61 6c 20 64 69 66 66 | subopti|mal diff|
|00002220| 20 6f 75 74 70 75 74 2e | 0d 20 20 20 49 74 20 63 | output.|.   It c|
|00002230| 61 6e 6e 6f 74 20 63 61 | 75 73 65 20 69 6e 63 6f |annot ca|use inco|
|00002240| 72 72 65 63 74 20 64 69 | 66 66 20 6f 75 74 70 75 |rrect di|ff outpu|
|00002250| 74 2e 20 20 2a 2f 0d 0d | 73 74 61 74 69 63 20 69 |t.  */..|static i|
|00002260| 6e 74 0d 64 69 61 67 20 | 28 69 6e 74 20 78 6f 66 |nt.diag |(int xof|
|00002270| 66 2c 20 69 6e 74 20 78 | 6c 69 6d 2c 20 69 6e 74 |f, int x|lim, int|
|00002280| 20 79 6f 66 66 2c 20 69 | 6e 74 20 79 6c 69 6d 2c | yoff, i|nt ylim,|
|00002290| 20 69 6e 74 20 6d 69 6e | 69 6d 61 6c 2c 20 73 74 | int min|imal, st|
|000022a0| 72 75 63 74 20 70 61 72 | 74 69 74 69 6f 6e 20 2a |ruct par|tition *|
|000022b0| 70 61 72 74 29 0d 7b 0d | 09 69 6e 74 20 2a 63 6f |part).{.|.int *co|
|000022c0| 6e 73 74 20 66 64 20 3d | 20 66 64 69 61 67 3b 09 |nst fd =| fdiag;.|
|000022d0| 09 09 09 2f 2a 20 47 69 | 76 65 20 74 68 65 20 63 |.../* Gi|ve the c|
|000022e0| 6f 6d 70 69 6c 65 72 20 | 61 20 63 68 61 6e 63 65 |ompiler |a chance|
|000022f0| 2e 20 2a 2f 0d 09 69 6e | 74 20 2a 63 6f 6e 73 74 |. */..in|t *const|
|00002300| 20 62 64 20 3d 20 62 64 | 69 61 67 3b 09 09 09 09 | bd = bd|iag;....|
|00002310| 2f 2a 20 41 64 64 69 74 | 69 6f 6e 61 6c 20 68 65 |/* Addit|ional he|
|00002320| 6c 70 20 66 6f 72 20 74 | 68 65 20 63 6f 6d 70 69 |lp for t|he compi|
|00002330| 6c 65 72 2e 20 2a 2f 0d | 09 69 6e 74 20 2a 63 6f |ler. */.|.int *co|
|00002340| 6e 73 74 20 78 76 20 3d | 20 78 76 65 63 3b 20 09 |nst xv =| xvec; .|
|00002350| 09 09 09 2f 2a 20 53 74 | 69 6c 6c 20 6d 6f 72 65 |.../* St|ill more|
|00002360| 20 68 65 6c 70 20 66 6f | 72 20 74 68 65 20 63 6f | help fo|r the co|
|00002370| 6d 70 69 6c 65 72 2e 20 | 2a 2f 0d 09 69 6e 74 20 |mpiler. |*/..int |
|00002380| 2a 63 6f 6e 73 74 20 79 | 76 20 3d 20 79 76 65 63 |*const y|v = yvec|
|00002390| 3b 20 09 09 09 09 2f 2a | 20 41 6e 64 20 6d 6f 72 |; ..../*| And mor|
|000023a0| 65 20 61 6e 64 20 6d 6f | 72 65 20 2e 20 2e 20 2e |e and mo|re . . .|
|000023b0| 20 2a 2f 0d 09 63 6f 6e | 73 74 20 69 6e 74 20 64 | */..con|st int d|
|000023c0| 6d 69 6e 20 3d 20 78 6f | 66 66 20 2d 20 79 6c 69 |min = xo|ff - yli|
|000023d0| 6d 3b 20 2f 2a 20 4d 69 | 6e 69 6d 75 6d 20 76 61 |m; /* Mi|nimum va|
|000023e0| 6c 69 64 20 64 69 61 67 | 6f 6e 61 6c 2e 20 2a 2f |lid diag|onal. */|
|000023f0| 0d 09 63 6f 6e 73 74 20 | 69 6e 74 20 64 6d 61 78 |..const |int dmax|
|00002400| 20 3d 20 78 6c 69 6d 20 | 2d 20 79 6f 66 66 3b 20 | = xlim |- yoff; |
|00002410| 2f 2a 20 4d 61 78 69 6d | 75 6d 20 76 61 6c 69 64 |/* Maxim|um valid|
|00002420| 20 64 69 61 67 6f 6e 61 | 6c 2e 20 2a 2f 0d 09 63 | diagona|l. */..c|
|00002430| 6f 6e 73 74 20 69 6e 74 | 20 66 6d 69 64 20 3d 20 |onst int| fmid = |
|00002440| 78 6f 66 66 20 2d 20 79 | 6f 66 66 3b 20 2f 2a 20 |xoff - y|off; /* |
|00002450| 43 65 6e 74 65 72 20 64 | 69 61 67 6f 6e 61 6c 20 |Center d|iagonal |
|00002460| 6f 66 20 74 6f 70 2d 64 | 6f 77 6e 20 73 65 61 72 |of top-d|own sear|
|00002470| 63 68 2e 20 2a 2f 0d 09 | 63 6f 6e 73 74 20 69 6e |ch. */..|const in|
|00002480| 74 20 62 6d 69 64 20 3d | 20 78 6c 69 6d 20 2d 20 |t bmid =| xlim - |
|00002490| 79 6c 69 6d 3b 20 2f 2a | 20 43 65 6e 74 65 72 20 |ylim; /*| Center |
|000024a0| 64 69 61 67 6f 6e 61 6c | 20 6f 66 20 62 6f 74 74 |diagonal| of bott|
|000024b0| 6f 6d 2d 75 70 20 73 65 | 61 72 63 68 2e 20 2a 2f |om-up se|arch. */|
|000024c0| 0d 09 69 6e 74 20 66 6d | 69 6e 20 3d 20 66 6d 69 |..int fm|in = fmi|
|000024d0| 64 2c 20 66 6d 61 78 20 | 3d 20 66 6d 69 64 3b 20 |d, fmax |= fmid; |
|000024e0| 2f 2a 20 4c 69 6d 69 74 | 73 20 6f 66 20 74 6f 70 |/* Limit|s of top|
|000024f0| 2d 64 6f 77 6e 20 73 65 | 61 72 63 68 2e 20 2a 2f |-down se|arch. */|
|00002500| 0d 09 69 6e 74 20 62 6d | 69 6e 20 3d 20 62 6d 69 |..int bm|in = bmi|
|00002510| 64 2c 20 62 6d 61 78 20 | 3d 20 62 6d 69 64 3b 20 |d, bmax |= bmid; |
|00002520| 2f 2a 20 4c 69 6d 69 74 | 73 20 6f 66 20 62 6f 74 |/* Limit|s of bot|
|00002530| 74 6f 6d 2d 75 70 20 73 | 65 61 72 63 68 2e 20 2a |tom-up s|earch. *|
|00002540| 2f 0d 09 69 6e 74 20 63 | 3b 09 09 09 09 09 09 09 |/..int c|;.......|
|00002550| 09 09 09 09 09 2f 2a 20 | 43 6f 73 74 2e 20 2a 2f |...../* |Cost. */|
|00002560| 0d 09 69 6e 74 20 6f 64 | 64 20 3d 20 28 66 6d 69 |..int od|d = (fmi|
|00002570| 64 20 2d 20 62 6d 69 64 | 29 20 26 20 31 3b 09 2f |d - bmid|) & 1;./|
|00002580| 2a 20 54 72 75 65 20 69 | 66 20 73 6f 75 74 68 65 |* True i|f southe|
|00002590| 61 73 74 20 63 6f 72 6e | 65 72 20 69 73 20 6f 6e |ast corn|er is on|
|000025a0| 20 61 6e 20 6f 64 64 0d | 09 09 09 09 09 09 09 09 | an odd.|........|
|000025b0| 09 09 09 09 09 09 09 09 | 09 20 64 69 61 67 6f 6e |........|. diagon|
|000025c0| 61 6c 20 77 69 74 68 20 | 72 65 73 70 65 63 74 20 |al with |respect |
|000025d0| 74 6f 20 74 68 65 20 6e | 6f 72 74 68 77 65 73 74 |to the n|orthwest|
|000025e0| 2e 20 2a 2f 0d 0d 09 66 | 64 5b 66 6d 69 64 5d 20 |. */...f|d[fmid] |
|000025f0| 3d 20 78 6f 66 66 3b 0d | 09 62 64 5b 62 6d 69 64 |= xoff;.|.bd[bmid|
|00002600| 5d 20 3d 20 78 6c 69 6d | 3b 0d 0d 09 66 6f 72 20 |] = xlim|;...for |
|00002610| 28 63 20 3d 20 31 3b 3b | 20 2b 2b 63 29 0d 09 09 |(c = 1;;| ++c)...|
|00002620| 7b 0d 09 09 09 69 6e 74 | 20 64 3b 09 09 09 09 09 |{....int| d;.....|
|00002630| 09 09 09 09 09 2f 2a 20 | 41 63 74 69 76 65 20 64 |...../* |Active d|
|00002640| 69 61 67 6f 6e 61 6c 2e | 20 2a 2f 0d 09 09 09 69 |iagonal.| */....i|
|00002650| 6e 74 20 62 69 67 5f 73 | 6e 61 6b 65 20 3d 20 30 |nt big_s|nake = 0|
|00002660| 3b 0d 0d 09 09 09 2f 2a | 20 45 78 74 65 6e 64 20 |;...../*| Extend |
|00002670| 74 68 65 20 74 6f 70 2d | 64 6f 77 6e 20 73 65 61 |the top-|down sea|
|00002680| 72 63 68 20 62 79 20 61 | 6e 20 65 64 69 74 20 73 |rch by a|n edit s|
|00002690| 74 65 70 20 69 6e 20 65 | 61 63 68 20 64 69 61 67 |tep in e|ach diag|
|000026a0| 6f 6e 61 6c 2e 20 2a 2f | 0d 09 09 09 66 6d 69 6e |onal. */|....fmin|
|000026b0| 20 3e 20 64 6d 69 6e 20 | 3f 20 66 64 5b 2d 2d 66 | > dmin |? fd[--f|
|000026c0| 6d 69 6e 20 2d 20 31 5d | 20 3d 20 2d 31 20 3a 20 |min - 1]| = -1 : |
|000026d0| 2b 2b 66 6d 69 6e 3b 0d | 09 09 09 66 6d 61 78 20 |++fmin;.|...fmax |
|000026e0| 3c 20 64 6d 61 78 20 3f | 20 66 64 5b 2b 2b 66 6d |< dmax ?| fd[++fm|
|000026f0| 61 78 20 2b 20 31 5d 20 | 3d 20 2d 31 20 3a 20 2d |ax + 1] |= -1 : -|
|00002700| 2d 66 6d 61 78 3b 0d 09 | 09 09 66 6f 72 20 28 64 |-fmax;..|..for (d|
|00002710| 20 3d 20 66 6d 61 78 3b | 20 64 20 3e 3d 20 66 6d | = fmax;| d >= fm|
|00002720| 69 6e 3b 20 64 20 2d 3d | 20 32 29 0d 09 09 09 09 |in; d -=| 2).....|
|00002730| 7b 0d 09 09 09 09 09 69 | 6e 74 20 78 2c 20 79 2c |{......i|nt x, y,|
|00002740| 20 6f 6c 64 78 2c 20 74 | 6c 6f 20 3d 20 66 64 5b | oldx, t|lo = fd[|
|00002750| 64 20 2d 20 31 5d 2c 20 | 74 68 69 20 3d 20 66 64 |d - 1], |thi = fd|
|00002760| 5b 64 20 2b 20 31 5d 3b | 0d 0d 09 09 09 09 09 69 |[d + 1];|.......i|
|00002770| 66 20 28 74 6c 6f 20 3e | 3d 20 74 68 69 29 0d 09 |f (tlo >|= thi)..|
|00002780| 09 09 09 09 09 78 20 3d | 20 74 6c 6f 20 2b 20 31 |.....x =| tlo + 1|
|00002790| 3b 0d 09 09 09 09 09 65 | 6c 73 65 0d 09 09 09 09 |;......e|lse.....|
|000027a0| 09 09 78 20 3d 20 74 68 | 69 3b 0d 09 09 09 09 09 |..x = th|i;......|
|000027b0| 6f 6c 64 78 20 3d 20 78 | 3b 0d 09 09 09 09 09 79 |oldx = x|;......y|
|000027c0| 20 3d 20 78 20 2d 20 64 | 3b 0d 09 09 09 09 09 77 | = x - d|;......w|
|000027d0| 68 69 6c 65 20 28 78 20 | 3c 20 78 6c 69 6d 20 26 |hile (x |< xlim &|
|000027e0| 26 20 79 20 3c 20 79 6c | 69 6d 20 26 26 20 78 76 |& y < yl|im && xv|
|000027f0| 5b 78 5d 20 3d 3d 20 79 | 76 5b 79 5d 29 0d 09 09 |[x] == y|v[y])...|
|00002800| 09 09 09 09 2b 2b 78 2c | 20 2b 2b 79 3b 0d 09 09 |....++x,| ++y;...|
|00002810| 09 09 09 69 66 20 28 78 | 20 2d 20 6f 6c 64 78 20 |...if (x| - oldx |
|00002820| 3e 20 53 4e 41 4b 45 5f | 4c 49 4d 49 54 29 0d 09 |> SNAKE_|LIMIT)..|
|00002830| 09 09 09 09 09 62 69 67 | 5f 73 6e 61 6b 65 20 3d |.....big|_snake =|
|00002840| 20 31 3b 0d 09 09 09 09 | 09 66 64 5b 64 5d 20 3d | 1;.....|.fd[d] =|
|00002850| 20 78 3b 0d 09 09 09 09 | 09 69 66 20 28 6f 64 64 | x;.....|.if (odd|
|00002860| 20 26 26 20 62 6d 69 6e | 20 3c 3d 20 64 20 26 26 | && bmin| <= d &&|
|00002870| 20 64 20 3c 3d 20 62 6d | 61 78 20 26 26 20 62 64 | d <= bm|ax && bd|
|00002880| 5b 64 5d 20 3c 3d 20 78 | 29 0d 09 09 09 09 09 09 |[d] <= x|).......|
|00002890| 7b 0d 09 09 09 09 09 09 | 09 70 61 72 74 2d 3e 78 |{.......|.part->x|
|000028a0| 6d 69 64 20 3d 20 78 3b | 0d 09 09 09 09 09 09 09 |mid = x;|........|
|000028b0| 70 61 72 74 2d 3e 79 6d | 69 64 20 3d 20 79 3b 0d |part->ym|id = y;.|
|000028c0| 09 09 09 09 09 09 09 70 | 61 72 74 2d 3e 6c 6f 5f |.......p|art->lo_|
|000028d0| 6d 69 6e 69 6d 61 6c 20 | 3d 20 70 61 72 74 2d 3e |minimal |= part->|
|000028e0| 68 69 5f 6d 69 6e 69 6d | 61 6c 20 3d 20 31 3b 0d |hi_minim|al = 1;.|
|000028f0| 09 09 09 09 09 09 09 72 | 65 74 75 72 6e 20 32 20 |.......r|eturn 2 |
|00002900| 2a 20 63 20 2d 20 31 3b | 0d 09 09 09 09 09 09 7d |* c - 1;|.......}|
|00002910| 0d 09 09 09 09 7d 0d 0d | 09 09 09 2f 2a 20 53 69 |.....}..|.../* Si|
|00002920| 6d 69 6c 61 72 20 65 78 | 74 65 6e 64 20 74 68 65 |milar ex|tend the|
|00002930| 20 62 6f 74 74 6f 6d 2d | 75 70 20 73 65 61 72 63 | bottom-|up searc|
|00002940| 68 2e 20 2a 2f 0d 09 09 | 09 62 6d 69 6e 20 3e 20 |h. */...|.bmin > |
|00002950| 64 6d 69 6e 20 3f 20 62 | 64 5b 2d 2d 62 6d 69 6e |dmin ? b|d[--bmin|
|00002960| 20 2d 20 31 5d 20 3d 20 | 49 4e 54 5f 4d 41 58 20 | - 1] = |INT_MAX |
|00002970| 3a 20 2b 2b 62 6d 69 6e | 3b 0d 09 09 09 62 6d 61 |: ++bmin|;....bma|
|00002980| 78 20 3c 20 64 6d 61 78 | 20 3f 20 62 64 5b 2b 2b |x < dmax| ? bd[++|
|00002990| 62 6d 61 78 20 2b 20 31 | 5d 20 3d 20 49 4e 54 5f |bmax + 1|] = INT_|
|000029a0| 4d 41 58 20 3a 20 2d 2d | 62 6d 61 78 3b 0d 09 09 |MAX : --|bmax;...|
|000029b0| 09 66 6f 72 20 28 64 20 | 3d 20 62 6d 61 78 3b 20 |.for (d |= bmax; |
|000029c0| 64 20 3e 3d 20 62 6d 69 | 6e 3b 20 64 20 2d 3d 20 |d >= bmi|n; d -= |
|000029d0| 32 29 0d 09 09 09 09 7b | 0d 09 09 09 09 09 69 6e |2).....{|......in|
|000029e0| 74 20 78 2c 20 79 2c 20 | 6f 6c 64 78 2c 20 74 6c |t x, y, |oldx, tl|
|000029f0| 6f 20 3d 20 62 64 5b 64 | 20 2d 20 31 5d 2c 20 74 |o = bd[d| - 1], t|
|00002a00| 68 69 20 3d 20 62 64 5b | 64 20 2b 20 31 5d 3b 0d |hi = bd[|d + 1];.|
|00002a10| 0d 09 09 09 09 09 69 66 | 20 28 74 6c 6f 20 3c 20 |......if| (tlo < |
|00002a20| 74 68 69 29 0d 09 09 09 | 09 09 09 78 20 3d 20 74 |thi)....|...x = t|
|00002a30| 6c 6f 3b 0d 09 09 09 09 | 09 65 6c 73 65 0d 09 09 |lo;.....|.else...|
|00002a40| 09 09 09 09 78 20 3d 20 | 74 68 69 20 2d 20 31 3b |....x = |thi - 1;|
|00002a50| 0d 09 09 09 09 09 6f 6c | 64 78 20 3d 20 78 3b 0d |......ol|dx = x;.|
|00002a60| 09 09 09 09 09 79 20 3d | 20 78 20 2d 20 64 3b 0d |.....y =| x - d;.|
|00002a70| 09 09 09 09 09 77 68 69 | 6c 65 20 28 78 20 3e 20 |.....whi|le (x > |
|00002a80| 78 6f 66 66 20 26 26 20 | 79 20 3e 20 79 6f 66 66 |xoff && |y > yoff|
|00002a90| 20 26 26 20 78 76 5b 78 | 20 2d 20 31 5d 20 3d 3d | && xv[x| - 1] ==|
|00002aa0| 20 79 76 5b 79 20 2d 20 | 31 5d 29 0d 09 09 09 09 | yv[y - |1]).....|
|00002ab0| 09 09 2d 2d 78 2c 20 2d | 2d 79 3b 0d 09 09 09 09 |..--x, -|-y;.....|
|00002ac0| 09 69 66 20 28 6f 6c 64 | 78 20 2d 20 78 20 3e 20 |.if (old|x - x > |
|00002ad0| 53 4e 41 4b 45 5f 4c 49 | 4d 49 54 29 0d 09 09 09 |SNAKE_LI|MIT)....|
|00002ae0| 09 09 09 62 69 67 5f 73 | 6e 61 6b 65 20 3d 20 31 |...big_s|nake = 1|
|00002af0| 3b 0d 09 09 09 09 09 62 | 64 5b 64 5d 20 3d 20 78 |;......b|d[d] = x|
|00002b00| 3b 0d 09 09 09 09 09 69 | 66 20 28 21 6f 64 64 20 |;......i|f (!odd |
|00002b10| 26 26 20 66 6d 69 6e 20 | 3c 3d 20 64 20 26 26 20 |&& fmin |<= d && |
|00002b20| 64 20 3c 3d 20 66 6d 61 | 78 20 26 26 20 78 20 3c |d <= fma|x && x <|
|00002b30| 3d 20 66 64 5b 64 5d 29 | 0d 09 09 09 09 09 09 7b |= fd[d])|.......{|
|00002b40| 0d 09 09 09 09 09 09 09 | 70 61 72 74 2d 3e 78 6d |........|part->xm|
|00002b50| 69 64 20 3d 20 78 3b 0d | 09 09 09 09 09 09 09 70 |id = x;.|.......p|
|00002b60| 61 72 74 2d 3e 79 6d 69 | 64 20 3d 20 79 3b 0d 09 |art->ymi|d = y;..|
|00002b70| 09 09 09 09 09 09 70 61 | 72 74 2d 3e 6c 6f 5f 6d |......pa|rt->lo_m|
|00002b80| 69 6e 69 6d 61 6c 20 3d | 20 70 61 72 74 2d 3e 68 |inimal =| part->h|
|00002b90| 69 5f 6d 69 6e 69 6d 61 | 6c 20 3d 20 31 3b 0d 09 |i_minima|l = 1;..|
|00002ba0| 09 09 09 09 09 09 72 65 | 74 75 72 6e 20 32 20 2a |......re|turn 2 *|
|00002bb0| 20 63 3b 0d 09 09 09 09 | 09 09 7d 0d 09 09 09 09 | c;.....|..}.....|
|00002bc0| 7d 0d 0d 20 20 20 20 20 | 20 69 66 20 28 6d 69 6e |}..     | if (min|
|00002bd0| 69 6d 61 6c 29 0d 09 09 | 09 09 63 6f 6e 74 69 6e |imal)...|..contin|
|00002be0| 75 65 3b 0d 0d 09 09 09 | 2f 2a 20 48 65 75 72 69 |ue;.....|/* Heuri|
|00002bf0| 73 74 69 63 3a 20 63 68 | 65 63 6b 20 6f 63 63 61 |stic: ch|eck occa|
|00002c00| 73 69 6f 6e 61 6c 6c 79 | 20 66 6f 72 20 61 20 64 |sionally| for a d|
|00002c10| 69 61 67 6f 6e 61 6c 20 | 74 68 61 74 20 68 61 73 |iagonal |that has|
|00002c20| 20 6d 61 64 65 0d 09 09 | 09 09 20 6c 6f 74 73 20 | made...|.. lots |
|00002c30| 6f 66 20 70 72 6f 67 72 | 65 73 73 20 63 6f 6d 70 |of progr|ess comp|
|00002c40| 61 72 65 64 20 77 69 74 | 68 20 74 68 65 20 65 64 |ared wit|h the ed|
|00002c50| 69 74 20 64 69 73 74 61 | 6e 63 65 2e 0d 09 09 09 |it dista|nce.....|
|00002c60| 09 20 49 66 20 77 65 20 | 68 61 76 65 20 61 6e 79 |. If we |have any|
|00002c70| 20 73 75 63 68 2c 20 66 | 69 6e 64 20 74 68 65 20 | such, f|ind the |
|00002c80| 6f 6e 65 20 74 68 61 74 | 20 68 61 73 20 6d 61 64 |one that| has mad|
|00002c90| 65 20 74 68 65 20 6d 6f | 73 74 0d 09 09 09 09 20 |e the mo|st..... |
|00002ca0| 70 72 6f 67 72 65 73 73 | 20 61 6e 64 20 72 65 74 |progress| and ret|
|00002cb0| 75 72 6e 20 69 74 20 61 | 73 20 69 66 20 69 74 20 |urn it a|s if it |
|00002cc0| 68 61 64 20 73 75 63 63 | 65 65 64 65 64 2e 0d 0d |had succ|eeded...|
|00002cd0| 09 09 09 09 20 57 69 74 | 68 20 74 68 69 73 20 68 |.... Wit|h this h|
|00002ce0| 65 75 72 69 73 74 69 63 | 2c 20 66 6f 72 20 66 69 |euristic|, for fi|
|00002cf0| 6c 65 73 20 77 69 74 68 | 20 61 20 63 6f 6e 73 74 |les with| a const|
|00002d00| 61 6e 74 20 73 6d 61 6c | 6c 20 64 65 6e 73 69 74 |ant smal|l densit|
|00002d10| 79 0d 09 09 09 09 20 6f | 66 20 63 68 61 6e 67 65 |y..... o|f change|
|00002d20| 73 2c 20 74 68 65 20 61 | 6c 67 6f 72 69 74 68 6d |s, the a|lgorithm|
|00002d30| 20 69 73 20 6c 69 6e 65 | 61 72 20 69 6e 20 74 68 | is line|ar in th|
|00002d40| 65 20 66 69 6c 65 20 73 | 69 7a 65 2e 09 2a 2f 0d |e file s|ize..*/.|
|00002d50| 0d 09 09 09 69 66 20 28 | 63 20 3e 20 32 30 30 20 |....if (|c > 200 |
|00002d60| 26 26 20 62 69 67 5f 73 | 6e 61 6b 65 29 0d 09 09 |&& big_s|nake)...|
|00002d70| 09 09 7b 0d 09 09 09 09 | 09 69 6e 74 20 62 65 73 |..{.....|.int bes|
|00002d80| 74 3b 0d 0d 09 09 09 09 | 09 62 65 73 74 20 3d 20 |t;......|.best = |
|00002d90| 30 3b 0d 09 09 09 09 09 | 66 6f 72 20 28 64 20 3d |0;......|for (d =|
|00002da0| 20 66 6d 61 78 3b 20 64 | 20 3e 3d 20 66 6d 69 6e | fmax; d| >= fmin|
|00002db0| 3b 20 64 20 2d 3d 20 32 | 29 0d 09 09 09 09 09 09 |; d -= 2|).......|
|00002dc0| 7b 0d 09 09 09 09 09 09 | 09 69 6e 74 20 64 64 20 |{.......|.int dd |
|00002dd0| 3d 20 64 20 2d 20 66 6d | 69 64 3b 0d 09 09 09 09 |= d - fm|id;.....|
|00002de0| 09 09 09 69 6e 74 20 78 | 20 3d 20 66 64 5b 64 5d |...int x| = fd[d]|
|00002df0| 3b 0d 09 09 09 09 09 09 | 09 69 6e 74 20 79 20 3d |;.......|.int y =|
|00002e00| 20 78 20 2d 20 64 3b 0d | 09 09 09 09 09 09 09 69 | x - d;.|.......i|
|00002e10| 6e 74 20 76 20 3d 20 28 | 78 20 2d 20 78 6f 66 66 |nt v = (|x - xoff|
|00002e20| 29 20 2a 20 32 20 2d 20 | 64 64 3b 0d 09 09 09 09 |) * 2 - |dd;.....|
|00002e30| 09 09 09 69 66 20 28 76 | 20 3e 20 31 32 20 2a 20 |...if (v| > 12 * |
|00002e40| 28 63 20 2b 20 28 64 64 | 20 3c 20 30 20 3f 20 2d |(c + (dd| < 0 ? -|
|00002e50| 64 64 20 3a 20 64 64 29 | 29 29 0d 09 09 09 09 09 |dd : dd)|))......|
|00002e60| 09 09 69 66 20 28 28 66 | 64 5b 64 5d 20 2d 20 78 |..if ((f|d[d] - x|
|00002e70| 6f 66 66 29 2a 32 20 2d | 20 64 64 20 3e 20 31 32 |off)*2 -| dd > 12|
|00002e80| 20 2a 20 28 63 20 2b 20 | 28 64 64 20 3e 20 30 20 | * (c + |(dd > 0 |
|00002e90| 3f 20 64 64 20 3a 20 2d | 64 64 29 29 29 0d 09 09 |? dd : -|dd)))...|
|00002ea0| 09 09 09 09 09 09 7b 0d | 09 09 09 09 09 09 09 09 |......{.|........|
|00002eb0| 09 69 66 20 28 76 20 3e | 20 62 65 73 74 0d 09 09 |.if (v >| best...|
|00002ec0| 09 09 09 09 09 09 09 09 | 09 26 26 20 78 6f 66 66 |........|.&& xoff|
|00002ed0| 20 2b 20 53 4e 41 4b 45 | 5f 4c 49 4d 49 54 20 3c | + SNAKE|_LIMIT <|
|00002ee0| 3d 20 78 20 26 26 20 78 | 20 3c 20 78 6c 69 6d 0d |= x && x| < xlim.|
|00002ef0| 09 09 09 09 09 09 09 09 | 09 09 09 26 26 20 79 6f |........|...&& yo|
|00002f00| 66 66 20 2b 20 53 4e 41 | 4b 45 5f 4c 49 4d 49 54 |ff + SNA|KE_LIMIT|
|00002f10| 20 3c 3d 20 79 20 26 26 | 20 79 20 3c 20 79 6c 69 | <= y &&| y < yli|
|00002f20| 6d 29 0d 09 09 09 09 09 | 09 09 09 09 09 7b 0d 09 |m)......|.....{..|
|00002f30| 09 09 09 09 09 09 09 09 | 09 09 2f 2a 20 57 65 20 |........|../* We |
|00002f40| 68 61 76 65 20 61 20 67 | 6f 6f 64 20 65 6e 6f 75 |have a g|ood enou|
|00002f50| 67 68 20 62 65 73 74 20 | 64 69 61 67 6f 6e 61 6c |gh best |diagonal|
|00002f60| 3b 0d 09 09 09 09 09 09 | 09 09 09 09 09 09 20 6e |;.......|...... n|
|00002f70| 6f 77 20 69 6e 73 69 73 | 74 20 74 68 61 74 20 69 |ow insis|t that i|
|00002f80| 74 20 65 6e 64 20 77 69 | 74 68 20 61 20 73 69 67 |t end wi|th a sig|
|00002f90| 6e 69 66 69 63 61 6e 74 | 20 73 6e 61 6b 65 2e 20 |nificant| snake. |
|00002fa0| 20 2a 2f 0d 09 09 09 09 | 09 09 09 09 09 09 09 69 | */.....|.......i|
|00002fb0| 6e 74 20 6b 3b 0d 0d 09 | 09 09 09 09 09 09 09 09 |nt k;...|........|
|00002fc0| 09 09 66 6f 72 20 28 6b | 20 3d 20 31 3b 20 78 76 |..for (k| = 1; xv|
|00002fd0| 5b 78 20 2d 20 6b 5d 20 | 3d 3d 20 79 76 5b 79 20 |[x - k] |== yv[y |
|00002fe0| 2d 20 6b 5d 3b 20 6b 2b | 2b 29 0d 09 09 09 09 09 |- k]; k+|+)......|
|00002ff0| 09 09 09 09 09 09 09 69 | 66 20 28 6b 20 3d 3d 20 |.......i|f (k == |
|00003000| 53 4e 41 4b 45 5f 4c 49 | 4d 49 54 29 0d 09 09 09 |SNAKE_LI|MIT)....|
|00003010| 09 09 09 09 09 09 09 09 | 09 09 7b 0d 09 09 09 09 |........|..{.....|
|00003020| 09 09 09 09 09 09 09 09 | 09 09 62 65 73 74 20 3d |........|..best =|
|00003030| 20 76 3b 0d 09 09 09 09 | 09 09 09 09 09 09 09 09 | v;.....|........|
|00003040| 09 09 70 61 72 74 2d 3e | 78 6d 69 64 20 3d 20 78 |..part->|xmid = x|
|00003050| 3b 0d 09 09 09 09 09 09 | 09 09 09 09 09 09 09 09 |;.......|........|
|00003060| 70 61 72 74 2d 3e 79 6d | 69 64 20 3d 20 79 3b 0d |part->ym|id = y;.|
|00003070| 09 09 09 09 09 09 09 09 | 09 09 09 09 09 09 62 72 |........|......br|
|00003080| 65 61 6b 3b 0d 09 09 09 | 09 09 09 09 09 09 09 09 |eak;....|........|
|00003090| 09 09 7d 0d 09 09 09 09 | 09 09 09 09 09 09 7d 0d |..}.....|......}.|
|000030a0| 09 09 09 09 09 09 09 09 | 7d 0d 09 09 09 09 09 09 |........|}.......|
|000030b0| 7d 0d 09 09 09 09 09 69 | 66 20 28 62 65 73 74 20 |}......i|f (best |
|000030c0| 3e 20 30 29 0d 09 09 09 | 09 09 09 7b 0d 09 09 09 |> 0)....|...{....|
|000030d0| 09 09 09 09 70 61 72 74 | 2d 3e 6c 6f 5f 6d 69 6e |....part|->lo_min|
|000030e0| 69 6d 61 6c 20 3d 20 31 | 3b 0d 09 09 09 09 09 09 |imal = 1|;.......|
|000030f0| 09 70 61 72 74 2d 3e 68 | 69 5f 6d 69 6e 69 6d 61 |.part->h|i_minima|
|00003100| 6c 20 3d 20 30 3b 0d 09 | 09 09 09 09 09 09 72 65 |l = 0;..|......re|
|00003110| 74 75 72 6e 20 32 20 2a | 20 63 20 2d 20 31 3b 0d |turn 2 *| c - 1;.|
|00003120| 09 09 09 09 09 09 7d 0d | 0d 09 09 09 09 09 62 65 |......}.|......be|
|00003130| 73 74 20 3d 20 30 3b 0d | 09 09 09 09 09 66 6f 72 |st = 0;.|.....for|
|00003140| 20 28 64 20 3d 20 62 6d | 61 78 3b 20 64 20 3e 3d | (d = bm|ax; d >=|
|00003150| 20 62 6d 69 6e 3b 20 64 | 20 2d 3d 20 32 29 0d 09 | bmin; d| -= 2)..|
|00003160| 09 09 09 09 09 7b 0d 09 | 09 09 09 09 09 09 69 6e |.....{..|......in|
|00003170| 74 20 64 64 20 3d 20 64 | 20 2d 20 62 6d 69 64 3b |t dd = d| - bmid;|
|00003180| 0d 09 09 09 09 09 09 09 | 69 6e 74 20 78 20 3d 20 |........|int x = |
|00003190| 62 64 5b 64 5d 3b 0d 09 | 09 09 09 09 09 09 69 6e |bd[d];..|......in|
|000031a0| 74 20 79 20 3d 20 78 20 | 2d 20 64 3b 0d 09 09 09 |t y = x |- d;....|
|000031b0| 09 09 09 09 69 6e 74 20 | 76 20 3d 20 28 78 6c 69 |....int |v = (xli|
|000031c0| 6d 20 2d 20 78 29 20 2a | 20 32 20 2b 20 64 64 3b |m - x) *| 2 + dd;|
|000031d0| 0d 09 09 09 09 09 09 09 | 69 66 20 28 76 20 3e 20 |........|if (v > |
|000031e0| 31 32 20 2a 20 28 63 20 | 2b 20 28 64 64 20 3c 20 |12 * (c |+ (dd < |
|000031f0| 30 20 3f 20 2d 64 64 20 | 3a 20 64 64 29 29 29 0d |0 ? -dd |: dd))).|
|00003200| 09 09 09 09 09 09 09 09 | 7b 0d 09 09 09 09 09 09 |........|{.......|
|00003210| 09 09 09 69 66 20 28 76 | 20 3e 20 62 65 73 74 0d |...if (v| > best.|
|00003220| 09 09 09 09 09 09 09 09 | 09 09 09 26 26 20 78 6f |........|...&& xo|
|00003230| 66 66 20 3c 20 78 20 26 | 26 20 78 20 3c 3d 20 78 |ff < x &|& x <= x|
|00003240| 6c 69 6d 20 2d 20 53 4e | 41 4b 45 5f 4c 49 4d 49 |lim - SN|AKE_LIMI|
|00003250| 54 0d 09 09 09 09 09 09 | 09 09 09 09 09 26 26 20 |T.......|.....&& |
|00003260| 79 6f 66 66 20 3c 20 79 | 20 26 26 20 79 20 3c 3d |yoff < y| && y <=|
|00003270| 20 79 6c 69 6d 20 2d 20 | 53 4e 41 4b 45 5f 4c 49 | ylim - |SNAKE_LI|
|00003280| 4d 49 54 29 0d 09 09 09 | 09 09 09 09 09 09 09 7b |MIT)....|.......{|
|00003290| 0d 09 09 09 09 09 09 09 | 09 09 09 09 2f 2a 20 57 |........|..../* W|
|000032a0| 65 20 68 61 76 65 20 61 | 20 67 6f 6f 64 20 65 6e |e have a| good en|
|000032b0| 6f 75 67 68 20 62 65 73 | 74 20 64 69 61 67 6f 6e |ough bes|t diagon|
|000032c0| 61 6c 3b 0d 09 09 09 09 | 09 09 09 09 09 09 09 09 |al;.....|........|
|000032d0| 20 6e 6f 77 20 69 6e 73 | 69 73 74 20 74 68 61 74 | now ins|ist that|
|000032e0| 20 69 74 20 65 6e 64 20 | 77 69 74 68 20 61 20 73 | it end |with a s|
|000032f0| 69 67 6e 69 66 69 63 61 | 6e 74 20 73 6e 61 6b 65 |ignifica|nt snake|
|00003300| 2e 20 20 2a 2f 0d 09 09 | 09 09 09 09 09 09 09 09 |.  */...|........|
|00003310| 09 69 6e 74 20 6b 3b 0d | 0d 09 09 09 09 09 09 09 |.int k;.|........|
|00003320| 09 09 09 09 66 6f 72 20 | 28 6b 20 3d 20 30 3b 20 |....for |(k = 0; |
|00003330| 78 76 5b 78 20 2b 20 6b | 5d 20 3d 3d 20 79 76 5b |xv[x + k|] == yv[|
|00003340| 79 20 2b 20 6b 5d 3b 20 | 6b 2b 2b 29 0d 09 09 09 |y + k]; |k++)....|
|00003350| 09 09 09 09 09 09 09 09 | 09 69 66 20 28 6b 20 3d |........|.if (k =|
|00003360| 3d 20 53 4e 41 4b 45 5f | 4c 49 4d 49 54 20 2d 20 |= SNAKE_|LIMIT - |
|00003370| 31 29 0d 09 09 09 09 09 | 09 09 09 09 09 09 09 09 |1)......|........|
|00003380| 7b 0d 09 09 09 09 09 09 | 09 09 09 09 09 09 09 09 |{.......|........|
|00003390| 62 65 73 74 20 3d 20 76 | 3b 0d 09 09 09 09 09 09 |best = v|;.......|
|000033a0| 09 09 09 09 09 09 09 09 | 70 61 72 74 2d 3e 78 6d |........|part->xm|
|000033b0| 69 64 20 3d 20 78 3b 0d | 09 09 09 09 09 09 09 09 |id = x;.|........|
|000033c0| 09 09 09 09 09 09 70 61 | 72 74 2d 3e 79 6d 69 64 |......pa|rt->ymid|
|000033d0| 20 3d 20 79 3b 0d 09 09 | 09 09 09 09 09 09 09 09 | = y;...|........|
|000033e0| 09 09 09 09 62 72 65 61 | 6b 3b 0d 09 09 09 09 09 |....brea|k;......|
|000033f0| 09 09 09 09 09 09 09 09 | 7d 0d 09 09 09 09 09 09 |........|}.......|
|00003400| 09 09 09 09 7d 0d 09 09 | 09 09 09 09 09 09 7d 0d |....}...|......}.|
|00003410| 09 09 09 09 09 09 7d 0d | 09 09 09 09 09 69 66 20 |......}.|.....if |
|00003420| 28 62 65 73 74 20 3e 20 | 30 29 0d 09 09 09 09 09 |(best > |0)......|
|00003430| 09 7b 0d 09 09 09 09 09 | 09 09 70 61 72 74 2d 3e |.{......|..part->|
|00003440| 6c 6f 5f 6d 69 6e 69 6d | 61 6c 20 3d 20 30 3b 0d |lo_minim|al = 0;.|
|00003450| 09 09 09 09 09 09 09 70 | 61 72 74 2d 3e 68 69 5f |.......p|art->hi_|
|00003460| 6d 69 6e 69 6d 61 6c 20 | 3d 20 31 3b 0d 09 09 09 |minimal |= 1;....|
|00003470| 09 09 09 09 72 65 74 75 | 72 6e 20 32 20 2a 20 63 |....retu|rn 2 * c|
|00003480| 20 2d 20 31 3b 0d 09 09 | 09 09 09 09 7d 0d 09 09 | - 1;...|....}...|
|00003490| 09 09 7d 0d 0d 09 09 09 | 2f 2a 20 48 65 75 72 69 |..}.....|/* Heuri|
|000034a0| 73 74 69 63 3a 20 69 66 | 20 77 65 27 76 65 20 67 |stic: if| we've g|
|000034b0| 6f 6e 65 20 77 65 6c 6c | 20 62 65 79 6f 6e 64 20 |one well| beyond |
|000034c0| 74 68 65 20 63 61 6c 6c | 20 6f 66 20 64 75 74 79 |the call| of duty|
|000034d0| 2c 0d 09 09 09 09 20 67 | 69 76 65 20 75 70 20 61 |,..... g|ive up a|
|000034e0| 6e 64 20 72 65 70 6f 72 | 74 20 68 61 6c 66 77 61 |nd repor|t halfwa|
|000034f0| 79 20 62 65 74 77 65 65 | 6e 20 6f 75 72 20 62 65 |y betwee|n our be|
|00003500| 73 74 20 72 65 73 75 6c | 74 73 20 73 6f 20 66 61 |st resul|ts so fa|
|00003510| 72 2e 20 20 2a 2f 0d 09 | 09 09 69 66 20 28 63 20 |r.  */..|..if (c |
|00003520| 3e 3d 20 74 6f 6f 5f 65 | 78 70 65 6e 73 69 76 65 |>= too_e|xpensive|
|00003530| 29 0d 09 09 09 09 7b 0d | 09 09 09 09 09 69 6e 74 |).....{.|.....int|
|00003540| 20 66 78 79 62 65 73 74 | 2c 20 66 78 62 65 73 74 | fxybest|, fxbest|
|00003550| 3b 0d 09 09 09 09 09 69 | 6e 74 20 62 78 79 62 65 |;......i|nt bxybe|
|00003560| 73 74 2c 20 62 78 62 65 | 73 74 3b 0d 0d 09 09 09 |st, bxbe|st;.....|
|00003570| 09 09 66 78 62 65 73 74 | 20 3d 20 62 78 62 65 73 |..fxbest| = bxbes|
|00003580| 74 20 3d 20 30 3b 20 20 | 2f 2a 20 50 61 63 69 66 |t = 0;  |/* Pacif|
|00003590| 79 20 60 67 63 63 20 2d | 57 61 6c 6c 27 2e 20 20 |y `gcc -|Wall'.  |
|000035a0| 2a 2f 0d 0d 09 09 09 09 | 09 2f 2a 20 46 69 6e 64 |*/......|./* Find|
|000035b0| 20 66 6f 72 77 61 72 64 | 20 64 69 61 67 6f 6e 61 | forward| diagona|
|000035c0| 6c 20 74 68 61 74 20 6d | 61 78 69 6d 69 7a 65 73 |l that m|aximizes|
|000035d0| 20 58 20 2b 20 59 2e 20 | 20 2a 2f 0d 09 09 09 09 | X + Y. | */.....|
|000035e0| 09 66 78 79 62 65 73 74 | 20 3d 20 2d 31 3b 0d 09 |.fxybest| = -1;..|
|000035f0| 09 09 09 09 66 6f 72 20 | 28 64 20 3d 20 66 6d 61 |....for |(d = fma|
|00003600| 78 3b 20 64 20 3e 3d 20 | 66 6d 69 6e 3b 20 64 20 |x; d >= |fmin; d |
|00003610| 2d 3d 20 32 29 0d 09 09 | 09 09 09 09 7b 0d 09 09 |-= 2)...|....{...|
|00003620| 09 09 09 09 09 69 6e 74 | 20 78 20 3d 20 28 66 64 |.....int| x = (fd|
|00003630| 5b 64 5d 20 3c 20 78 6c | 69 6d 20 3f 20 66 64 5b |[d] < xl|im ? fd[|
|00003640| 64 5d 20 3a 20 78 6c 69 | 6d 29 3b 0d 09 09 09 09 |d] : xli|m);.....|
|00003650| 09 09 09 69 6e 74 20 79 | 20 3d 20 78 20 2d 20 64 |...int y| = x - d|
|00003660| 3b 0d 09 09 09 09 09 09 | 09 69 66 20 28 79 6c 69 |;.......|.if (yli|
|00003670| 6d 20 3c 20 79 29 0d 09 | 09 09 09 09 09 09 09 78 |m < y)..|.......x|
|00003680| 20 3d 20 79 6c 69 6d 20 | 2b 20 64 2c 20 79 20 3d | = ylim |+ d, y =|
|00003690| 20 79 6c 69 6d 3b 0d 09 | 09 09 09 09 09 09 69 66 | ylim;..|......if|
|000036a0| 20 28 66 78 79 62 65 73 | 74 20 3c 20 78 20 2b 20 | (fxybes|t < x + |
|000036b0| 79 29 0d 09 09 09 09 09 | 09 09 09 7b 0d 09 09 09 |y)......|...{....|
|000036c0| 09 09 09 09 09 09 66 78 | 79 62 65 73 74 20 3d 20 |......fx|ybest = |
|000036d0| 78 20 2b 20 79 3b 0d 09 | 09 09 09 09 09 09 09 09 |x + y;..|........|
|000036e0| 66 78 62 65 73 74 20 3d | 20 78 3b 0d 09 09 09 09 |fxbest =| x;.....|
|000036f0| 09 09 09 09 7d 0d 09 09 | 09 09 09 09 7d 0d 0d 09 |....}...|....}...|
|00003700| 09 09 09 09 2f 2a 20 46 | 69 6e 64 20 62 61 63 6b |..../* F|ind back|
|00003710| 77 61 72 64 20 64 69 61 | 67 6f 6e 61 6c 20 74 68 |ward dia|gonal th|
|00003720| 61 74 20 6d 69 6e 69 6d | 69 7a 65 73 20 58 20 2b |at minim|izes X +|
|00003730| 20 59 2e 20 20 2a 2f 0d | 09 09 09 09 09 62 78 79 | Y.  */.|.....bxy|
|00003740| 62 65 73 74 20 3d 20 49 | 4e 54 5f 4d 41 58 3b 0d |best = I|NT_MAX;.|
|00003750| 09 09 09 09 09 66 6f 72 | 20 28 64 20 3d 20 62 6d |.....for| (d = bm|
|00003760| 61 78 3b 20 64 20 3e 3d | 20 62 6d 69 6e 3b 20 64 |ax; d >=| bmin; d|
|00003770| 20 2d 3d 20 32 29 0d 09 | 09 09 09 09 09 7b 0d 09 | -= 2)..|.....{..|
|00003780| 09 09 09 09 09 09 69 6e | 74 20 78 20 3d 20 28 78 |......in|t x = (x|
|00003790| 6f 66 66 20 3e 20 62 64 | 5b 64 5d 20 3f 20 78 6f |off > bd|[d] ? xo|
|000037a0| 66 66 20 3a 20 62 64 5b | 64 5d 29 3b 0d 09 09 09 |ff : bd[|d]);....|
|000037b0| 09 09 09 09 69 6e 74 20 | 79 20 3d 20 78 20 2d 20 |....int |y = x - |
|000037c0| 64 3b 0d 09 09 09 09 09 | 09 09 69 66 20 28 79 20 |d;......|..if (y |
|000037d0| 3c 20 79 6f 66 66 29 0d | 09 09 09 09 09 09 09 09 |< yoff).|........|
|000037e0| 78 20 3d 20 79 6f 66 66 | 20 2b 20 64 2c 20 79 20 |x = yoff| + d, y |
|000037f0| 3d 20 79 6f 66 66 3b 0d | 09 09 09 09 09 09 09 69 |= yoff;.|.......i|
|00003800| 66 20 28 78 20 2b 20 79 | 20 3c 20 62 78 79 62 65 |f (x + y| < bxybe|
|00003810| 73 74 29 0d 09 09 09 09 | 09 09 09 09 7b 0d 09 09 |st).....|....{...|
|00003820| 09 09 09 09 09 09 09 62 | 78 79 62 65 73 74 20 3d |.......b|xybest =|
|00003830| 20 78 20 2b 20 79 3b 0d | 09 09 09 09 09 09 09 09 | x + y;.|........|
|00003840| 09 62 78 62 65 73 74 20 | 3d 20 78 3b 0d 09 09 09 |.bxbest |= x;....|
|00003850| 09 09 09 09 09 7d 0d 09 | 09 09 09 09 09 7d 0d 0d |.....}..|.....}..|
|00003860| 09 09 09 09 09 2f 2a 20 | 55 73 65 20 74 68 65 20 |...../* |Use the |
|00003870| 62 65 74 74 65 72 20 6f | 66 20 74 68 65 20 74 77 |better o|f the tw|
|00003880| 6f 20 64 69 61 67 6f 6e | 61 6c 73 2e 20 20 2a 2f |o diagon|als.  */|
|00003890| 0d 09 09 09 09 09 69 66 | 20 28 28 78 6c 69 6d 20 |......if| ((xlim |
|000038a0| 2b 20 79 6c 69 6d 29 20 | 2d 20 62 78 79 62 65 73 |+ ylim) |- bxybes|
|000038b0| 74 20 3c 20 66 78 79 62 | 65 73 74 20 2d 20 28 78 |t < fxyb|est - (x|
|000038c0| 6f 66 66 20 2b 20 79 6f | 66 66 29 29 0d 09 09 09 |off + yo|ff))....|
|000038d0| 09 09 09 7b 0d 09 09 09 | 09 09 09 09 70 61 72 74 |...{....|....part|
|000038e0| 2d 3e 78 6d 69 64 20 3d | 20 66 78 62 65 73 74 3b |->xmid =| fxbest;|
|000038f0| 0d 09 09 09 09 09 09 09 | 70 61 72 74 2d 3e 79 6d |........|part->ym|
|00003900| 69 64 20 3d 20 66 78 79 | 62 65 73 74 20 2d 20 66 |id = fxy|best - f|
|00003910| 78 62 65 73 74 3b 0d 09 | 09 09 09 09 09 09 70 61 |xbest;..|......pa|
|00003920| 72 74 2d 3e 6c 6f 5f 6d | 69 6e 69 6d 61 6c 20 3d |rt->lo_m|inimal =|
|00003930| 20 31 3b 0d 09 09 09 09 | 09 09 09 70 61 72 74 2d | 1;.....|...part-|
|00003940| 3e 68 69 5f 6d 69 6e 69 | 6d 61 6c 20 3d 20 30 3b |>hi_mini|mal = 0;|
|00003950| 0d 09 09 09 09 09 09 7d | 0d 09 09 09 09 09 65 6c |.......}|......el|
|00003960| 73 65 0d 09 09 09 09 09 | 09 7b 0d 09 09 09 09 09 |se......|.{......|
|00003970| 09 09 70 61 72 74 2d 3e | 78 6d 69 64 20 3d 20 62 |..part->|xmid = b|
|00003980| 78 62 65 73 74 3b 0d 09 | 09 09 09 09 09 09 70 61 |xbest;..|......pa|
|00003990| 72 74 2d 3e 79 6d 69 64 | 20 3d 20 62 78 79 62 65 |rt->ymid| = bxybe|
|000039a0| 73 74 20 2d 20 62 78 62 | 65 73 74 3b 0d 09 09 09 |st - bxb|est;....|
|000039b0| 09 09 09 09 70 61 72 74 | 2d 3e 6c 6f 5f 6d 69 6e |....part|->lo_min|
|000039c0| 69 6d 61 6c 20 3d 20 30 | 3b 0d 09 09 09 09 09 09 |imal = 0|;.......|
|000039d0| 09 70 61 72 74 2d 3e 68 | 69 5f 6d 69 6e 69 6d 61 |.part->h|i_minima|
|000039e0| 6c 20 3d 20 31 3b 0d 09 | 09 09 09 09 09 7d 0d 09 |l = 1;..|.....}..|
|000039f0| 09 09 09 09 72 65 74 75 | 72 6e 20 32 20 2a 20 63 |....retu|rn 2 * c|
|00003a00| 20 2d 20 31 3b 0d 09 09 | 09 09 7d 0d 09 09 7d 0d | - 1;...|..}...}.|
|00003a10| 7d 0d 0d 2f 2a 20 52 65 | 70 6f 72 74 20 74 68 65 |}../* Re|port the|
|00003a20| 20 64 69 66 66 65 72 65 | 6e 63 65 73 20 6f 66 20 | differe|nces of |
|00003a30| 74 77 6f 20 66 69 6c 65 | 73 2e 20 2a 2f 0d 0d 76 |two file|s. */..v|
|00003a40| 6f 69 64 0d 64 69 66 66 | 5f 32 5f 66 69 6c 65 73 |oid.diff|_2_files|
|00003a50| 20 28 72 65 67 69 73 74 | 65 72 20 73 74 72 75 63 | (regist|er struc|
|00003a60| 74 20 66 69 6c 65 5f 64 | 61 74 61 20 2a 66 69 6c |t file_d|ata *fil|
|00003a70| 65 30 50 74 72 2c 20 72 | 65 67 69 73 74 65 72 20 |e0Ptr, r|egister |
|00003a80| 73 74 72 75 63 74 20 66 | 69 6c 65 5f 64 61 74 61 |struct f|ile_data|
|00003a90| 20 2a 66 69 6c 65 31 50 | 74 72 29 0d 7b 0d 09 69 | *file1P|tr).{..i|
|00003aa0| 6e 74 20 09 09 09 09 09 | 20 64 69 61 67 73 3b 0d |nt .....| diags;.|
|00003ab0| 20 20 69 6e 74 09 09 09 | 09 09 09 20 69 3b 0d 09 |  int...|... i;..|
|00003ac0| 73 74 72 75 63 74 20 63 | 68 61 6e 67 65 20 2a 6e |struct c|hange *n|
|00003ad0| 65 78 74 53 63 72 69 70 | 74 50 74 72 3b 0d 09 73 |extScrip|tPtr;..s|
|00003ae0| 74 72 75 63 74 20 63 68 | 61 6e 67 65 20 2a 73 63 |truct ch|ange *sc|
|00003af0| 72 69 70 74 50 74 72 3b | 0d 0d 09 72 65 61 64 5f |riptPtr;|...read_|
|00003b00| 66 69 6c 65 73 20 28 66 | 69 6c 65 30 50 74 72 2c |files (f|ile0Ptr,|
|00003b10| 20 66 69 6c 65 31 50 74 | 72 29 3b 0d 0d 09 73 63 | file1Pt|r);...sc|
|00003b20| 72 69 70 74 50 74 72 20 | 3d 20 66 69 6c 65 31 50 |riptPtr |= file1P|
|00003b30| 74 72 2d 3e 73 63 72 69 | 70 74 50 74 72 3b 0d 09 |tr->scri|ptPtr;..|
|00003b40| 77 68 69 6c 65 20 28 73 | 63 72 69 70 74 50 74 72 |while (s|criptPtr|
|00003b50| 20 21 3d 20 4e 55 4c 4c | 29 20 7b 0d 09 09 6e 65 | != NULL|) {...ne|
|00003b60| 78 74 53 63 72 69 70 74 | 50 74 72 20 3d 20 73 63 |xtScript|Ptr = sc|
|00003b70| 72 69 70 74 50 74 72 2d | 3e 6c 69 6e 6b 3b 0d 09 |riptPtr-|>link;..|
|00003b80| 09 66 72 65 65 20 28 73 | 63 72 69 70 74 50 74 72 |.free (s|criptPtr|
|00003b90| 29 3b 0d 09 09 73 63 72 | 69 70 74 50 74 72 20 3d |);...scr|iptPtr =|
|00003ba0| 20 6e 65 78 74 53 63 72 | 69 70 74 50 74 72 3b 0d | nextScr|iptPtr;.|
|00003bb0| 09 7d 0d 09 66 69 6c 65 | 31 50 74 72 2d 3e 73 63 |.}..file|1Ptr->sc|
|00003bc0| 72 69 70 74 50 74 72 20 | 3d 20 4e 55 4c 4c 3b 0d |riptPtr |= NULL;.|
|00003bd0| 0d 09 69 66 20 28 66 69 | 6c 65 30 50 74 72 2d 3e |..if (fi|le0Ptr->|
|00003be0| 62 75 66 66 65 72 20 21 | 3d 20 4e 55 4c 4c 20 26 |buffer !|= NULL &|
|00003bf0| 26 20 66 69 6c 65 31 50 | 74 72 2d 3e 62 75 66 66 |& file1P|tr->buff|
|00003c00| 65 72 20 21 3d 20 4e 55 | 4c 4c 29 20 7b 0d 09 2f |er != NU|LL) {../|
|00003c10| 2a 0d 09 20 2a 20 41 6c | 6c 6f 63 61 74 65 20 76 |*.. * Al|locate v|
|00003c20| 65 63 74 6f 72 73 20 66 | 6f 72 20 74 68 65 20 72 |ectors f|or the r|
|00003c30| 65 73 75 6c 74 73 20 6f | 66 20 63 6f 6d 70 61 72 |esults o|f compar|
|00003c40| 69 73 6f 6e 3a 0d 09 20 | 2a 20 61 20 66 6c 61 67 |ison:.. |* a flag|
|00003c50| 20 66 6f 72 20 65 61 63 | 68 20 6c 69 6e 65 20 6f | for eac|h line o|
|00003c60| 66 20 65 61 63 68 20 66 | 69 6c 65 2c 20 73 61 79 |f each f|ile, say|
|00003c70| 69 6e 67 20 77 68 65 74 | 68 65 72 20 74 68 61 74 |ing whet|her that|
|00003c80| 20 6c 69 6e 65 0d 09 20 | 2a 20 69 73 20 61 6e 20 | line.. |* is an |
|00003c90| 69 6e 73 65 72 74 69 6f | 6e 20 6f 72 20 64 65 6c |insertio|n or del|
|00003ca0| 65 74 69 6f 6e 2e 0d 09 | 20 2a 20 41 6c 6c 6f 63 |etion...| * Alloc|
|00003cb0| 61 74 65 20 61 6e 20 65 | 78 74 72 61 20 65 6c 65 |ate an e|xtra ele|
|00003cc0| 6d 65 6e 74 2c 20 61 6c | 77 61 79 73 20 7a 65 72 |ment, al|ways zer|
|00003cd0| 6f 2c 20 61 74 20 65 61 | 63 68 20 65 6e 64 20 6f |o, at ea|ch end o|
|00003ce0| 66 20 65 61 63 68 20 76 | 65 63 74 6f 72 2e 0d 09 |f each v|ector...|
|00003cf0| 20 2a 2f 0d 09 09 69 66 | 20 28 66 69 6c 65 30 50 | */...if| (file0P|
|00003d00| 74 72 2d 3e 63 68 61 6e | 67 65 64 5f 66 6c 61 67 |tr->chan|ged_flag|
|00003d10| 20 3d 3d 20 4e 55 4c 4c | 29 20 7b 0d 09 09 09 66 | == NULL|) {....f|
|00003d20| 69 6c 65 30 50 74 72 2d | 3e 63 68 61 6e 67 65 64 |ile0Ptr-|>changed|
|00003d30| 5f 66 6c 61 67 20 3d 20 | 28 63 68 61 72 20 2a 29 |_flag = |(char *)|
|00003d40| 20 78 6d 61 6c 6c 6f 63 | 20 28 66 69 6c 65 30 50 | xmalloc| (file0P|
|00003d50| 74 72 2d 3e 62 75 66 66 | 65 72 65 64 5f 6c 69 6e |tr->buff|ered_lin|
|00003d60| 65 73 20 2b 20 32 29 3b | 0d 09 09 09 66 69 6c 65 |es + 2);|....file|
|00003d70| 30 50 74 72 2d 3e 63 68 | 61 6e 67 65 64 5f 66 6c |0Ptr->ch|anged_fl|
|00003d80| 61 67 2b 2b 3b 0d 09 09 | 7d 0d 0d 09 09 69 66 20 |ag++;...|}....if |
|00003d90| 28 66 69 6c 65 31 50 74 | 72 2d 3e 63 68 61 6e 67 |(file1Pt|r->chang|
|00003da0| 65 64 5f 66 6c 61 67 20 | 3d 3d 20 4e 55 4c 4c 29 |ed_flag |== NULL)|
|00003db0| 20 7b 0d 09 09 09 66 69 | 6c 65 31 50 74 72 2d 3e | {....fi|le1Ptr->|
|00003dc0| 63 68 61 6e 67 65 64 5f | 66 6c 61 67 20 3d 20 28 |changed_|flag = (|
|00003dd0| 63 68 61 72 20 2a 29 20 | 78 6d 61 6c 6c 6f 63 20 |char *) |xmalloc |
|00003de0| 28 66 69 6c 65 31 50 74 | 72 2d 3e 62 75 66 66 65 |(file1Pt|r->buffe|
|00003df0| 72 65 64 5f 6c 69 6e 65 | 73 20 2b 20 32 29 3b 0d |red_line|s + 2);.|
|00003e00| 09 09 09 66 69 6c 65 31 | 50 74 72 2d 3e 63 68 61 |...file1|Ptr->cha|
|00003e10| 6e 67 65 64 5f 66 6c 61 | 67 2b 2b 3b 0d 09 09 7d |nged_fla|g++;...}|
|00003e20| 0d 0d 09 09 62 7a 65 72 | 6f 20 28 66 69 6c 65 30 |....bzer|o (file0|
|00003e30| 50 74 72 2d 3e 63 68 61 | 6e 67 65 64 5f 66 6c 61 |Ptr->cha|nged_fla|
|00003e40| 67 20 2d 20 31 2c 20 66 | 69 6c 65 30 50 74 72 2d |g - 1, f|ile0Ptr-|
|00003e50| 3e 62 75 66 66 65 72 65 | 64 5f 6c 69 6e 65 73 20 |>buffere|d_lines |
|00003e60| 2b 20 32 29 3b 0d 09 09 | 62 7a 65 72 6f 20 28 66 |+ 2);...|bzero (f|
|00003e70| 69 6c 65 31 50 74 72 2d | 3e 63 68 61 6e 67 65 64 |ile1Ptr-|>changed|
|00003e80| 5f 66 6c 61 67 20 2d 20 | 31 2c 20 66 69 6c 65 31 |_flag - |1, file1|
|00003e90| 50 74 72 2d 3e 62 75 66 | 66 65 72 65 64 5f 6c 69 |Ptr->buf|fered_li|
|00003ea0| 6e 65 73 20 2b 20 32 29 | 3b 0d 20 2f 2a 0d 09 2a |nes + 2)|;. /*..*|
|00003eb0| 20 53 6f 6d 65 20 6c 69 | 6e 65 73 20 61 72 65 20 | Some li|nes are |
|00003ec0| 6f 62 76 69 6f 75 73 6c | 79 20 69 6e 73 65 72 74 |obviousl|y insert|
|00003ed0| 69 6f 6e 73 20 6f 72 20 | 64 65 6c 65 74 69 6f 6e |ions or |deletion|
|00003ee0| 73 0d 09 2a 20 62 65 63 | 61 75 73 65 20 74 68 65 |s..* bec|ause the|
|00003ef0| 79 20 64 6f 6e 27 74 20 | 6d 61 74 63 68 20 61 6e |y don't |match an|
|00003f00| 79 74 68 69 6e 67 2e 20 | 20 44 65 74 65 63 74 20 |ything. | Detect |
|00003f10| 74 68 65 6d 20 6e 6f 77 | 2c 0d 09 2a 20 61 6e 64 |them now|,..* and|
|00003f20| 20 61 76 6f 69 64 20 65 | 76 65 6e 20 74 68 69 6e | avoid e|ven thin|
|00003f30| 6b 69 6e 67 20 61 62 6f | 75 74 20 74 68 65 6d 20 |king abo|ut them |
|00003f40| 69 6e 20 74 68 65 20 6d | 61 69 6e 20 63 6f 6d 70 |in the m|ain comp|
|00003f50| 61 72 69 73 6f 6e 20 61 | 6c 67 6f 72 69 74 68 6d |arison a|lgorithm|
|00003f60| 2e 0d 09 2a 2f 0d 09 09 | 64 69 73 63 61 72 64 5f |...*/...|discard_|
|00003f70| 63 6f 6e 66 75 73 69 6e | 67 5f 6c 69 6e 65 73 20 |confusin|g_lines |
|00003f80| 28 66 69 6c 65 30 50 74 | 72 2c 20 66 69 6c 65 31 |(file0Pt|r, file1|
|00003f90| 50 74 72 29 3b 0d 20 2f | 2a 0d 09 2a 20 4e 6f 77 |Ptr);. /|*..* Now|
|00003fa0| 20 64 6f 20 74 68 65 20 | 6d 61 69 6e 20 63 6f 6d | do the |main com|
|00003fb0| 70 61 72 69 73 6f 6e 20 | 61 6c 67 6f 72 69 74 68 |parison |algorith|
|00003fc0| 6d 2c 20 63 6f 6e 73 69 | 64 65 72 69 6e 67 20 6a |m, consi|dering j|
|00003fd0| 75 73 74 20 74 68 65 0d | 09 2a 20 75 6e 64 69 73 |ust the.|.* undis|
|00003fe0| 63 61 72 64 65 64 20 6c | 69 6e 65 73 2e 0d 09 2a |carded l|ines...*|
|00003ff0| 2f 0d 09 09 78 76 65 63 | 20 3d 20 66 69 6c 65 30 |/...xvec| = file0|
|00004000| 50 74 72 2d 3e 75 6e 64 | 69 73 63 61 72 64 65 64 |Ptr->und|iscarded|
|00004010| 3b 0d 09 09 79 76 65 63 | 20 3d 20 66 69 6c 65 31 |;...yvec| = file1|
|00004020| 50 74 72 2d 3e 75 6e 64 | 69 73 63 61 72 64 65 64 |Ptr->und|iscarded|
|00004030| 3b 0d 09 09 64 69 61 67 | 73 20 3d 20 66 69 6c 65 |;...diag|s = file|
|00004040| 30 50 74 72 2d 3e 6e 6f | 6e 64 69 73 63 61 72 64 |0Ptr->no|ndiscard|
|00004050| 65 64 5f 6c 69 6e 65 73 | 20 2b 20 66 69 6c 65 31 |ed_lines| + file1|
|00004060| 50 74 72 2d 3e 6e 6f 6e | 64 69 73 63 61 72 64 65 |Ptr->non|discarde|
|00004070| 64 5f 6c 69 6e 65 73 20 | 2b 20 33 3b 0d 09 09 66 |d_lines |+ 3;...f|
|00004080| 64 69 61 67 20 3d 20 28 | 69 6e 74 20 2a 29 20 78 |diag = (|int *) x|
|00004090| 6d 61 6c 6c 6f 63 20 28 | 64 69 61 67 73 20 2a 20 |malloc (|diags * |
|000040a0| 28 32 20 2a 20 73 69 7a | 65 6f 66 20 28 69 6e 74 |(2 * siz|eof (int|
|000040b0| 29 29 29 3b 0d 09 09 62 | 64 69 61 67 20 3d 20 66 |)));...b|diag = f|
|000040c0| 64 69 61 67 20 2b 20 64 | 69 61 67 73 3b 0d 09 09 |diag + d|iags;...|
|000040d0| 66 64 69 61 67 20 2b 3d | 20 66 69 6c 65 31 50 74 |fdiag +=| file1Pt|
|000040e0| 72 2d 3e 6e 6f 6e 64 69 | 73 63 61 72 64 65 64 5f |r->nondi|scarded_|
|000040f0| 6c 69 6e 65 73 20 2b 20 | 31 3b 0d 09 09 62 64 69 |lines + |1;...bdi|
|00004100| 61 67 20 2b 3d 20 66 69 | 6c 65 31 50 74 72 2d 3e |ag += fi|le1Ptr->|
|00004110| 6e 6f 6e 64 69 73 63 61 | 72 64 65 64 5f 6c 69 6e |nondisca|rded_lin|
|00004120| 65 73 20 2b 20 31 3b 0d | 0d 20 20 20 20 2f 2a 20 |es + 1;.|.    /* |
|00004130| 53 65 74 20 54 4f 4f 5f | 45 58 50 45 4e 53 49 56 |Set TOO_|EXPENSIV|
|00004140| 45 20 74 6f 20 62 65 20 | 61 70 70 72 6f 78 69 6d |E to be |approxim|
|00004150| 61 74 65 20 73 71 75 61 | 72 65 20 72 6f 6f 74 20 |ate squa|re root |
|00004160| 6f 66 20 69 6e 70 75 74 | 20 73 69 7a 65 2c 0d 09 |of input| size,..|
|00004170| 09 09 20 62 6f 75 6e 64 | 65 64 20 62 65 6c 6f 77 |.. bound|ed below|
|00004180| 20 62 79 20 32 35 36 2e | 20 20 2a 2f 0d 09 09 74 | by 256.|  */...t|
|00004190| 6f 6f 5f 65 78 70 65 6e | 73 69 76 65 20 3d 20 31 |oo_expen|sive = 1|
|000041a0| 3b 0d 09 09 66 6f 72 20 | 28 69 20 3d 20 66 69 6c |;...for |(i = fil|
|000041b0| 65 30 50 74 72 2d 3e 6e | 6f 6e 64 69 73 63 61 72 |e0Ptr->n|ondiscar|
|000041c0| 64 65 64 5f 6c 69 6e 65 | 73 20 2b 20 66 69 6c 65 |ded_line|s + file|
|000041d0| 31 50 74 72 2d 3e 6e 6f | 6e 64 69 73 63 61 72 64 |1Ptr->no|ndiscard|
|000041e0| 65 64 5f 6c 69 6e 65 73 | 3b 20 69 20 21 3d 20 30 |ed_lines|; i != 0|
|000041f0| 3b 20 69 20 3e 3e 3d 20 | 32 29 0d 09 09 09 74 6f |; i >>= |2)....to|
|00004200| 6f 5f 65 78 70 65 6e 73 | 69 76 65 20 3c 3c 3d 20 |o_expens|ive <<= |
|00004210| 31 3b 0d 09 09 74 6f 6f | 5f 65 78 70 65 6e 73 69 |1;...too|_expensi|
|00004220| 76 65 20 3d 20 28 32 35 | 36 20 3e 20 74 6f 6f 5f |ve = (25|6 > too_|
|00004230| 65 78 70 65 6e 73 69 76 | 65 20 3f 20 32 35 36 20 |expensiv|e ? 256 |
|00004240| 3a 20 74 6f 6f 5f 65 78 | 70 65 6e 73 69 76 65 29 |: too_ex|pensive)|
|00004250| 3b 0d 0d 09 09 09 63 6f | 6d 70 61 72 65 73 65 71 |;.....co|mpareseq|
|00004260| 20 28 66 69 6c 65 30 50 | 74 72 2c 20 66 69 6c 65 | (file0P|tr, file|
|00004270| 31 50 74 72 2c 20 30 2c | 20 66 69 6c 65 30 50 74 |1Ptr, 0,| file0Pt|
|00004280| 72 2d 3e 6e 6f 6e 64 69 | 73 63 61 72 64 65 64 5f |r->nondi|scarded_|
|00004290| 6c 69 6e 65 73 2c 20 30 | 2c 20 66 69 6c 65 31 50 |lines, 0|, file1P|
|000042a0| 74 72 2d 3e 6e 6f 6e 64 | 69 73 63 61 72 64 65 64 |tr->nond|iscarded|
|000042b0| 5f 6c 69 6e 65 73 2c 20 | 2f 2a 6d 69 6e 69 6d 61 |_lines, |/*minima|
|000042c0| 6c 20 69 73 2a 2f 20 31 | 29 3b 0d 0d 09 09 66 72 |l is*/ 1|);....fr|
|000042d0| 65 65 20 28 66 64 69 61 | 67 20 2d 20 28 66 69 6c |ee (fdia|g - (fil|
|000042e0| 65 31 50 74 72 2d 3e 6e | 6f 6e 64 69 73 63 61 72 |e1Ptr->n|ondiscar|
|000042f0| 64 65 64 5f 6c 69 6e 65 | 73 20 2b 20 31 29 29 3b |ded_line|s + 1));|
|00004300| 0d 20 2f 2a 0d 09 2a 20 | 4d 6f 64 69 66 79 20 74 |. /*..* |Modify t|
|00004310| 68 65 20 72 65 73 75 6c | 74 73 20 73 6c 69 67 68 |he resul|ts sligh|
|00004320| 74 6c 79 20 74 6f 20 6d | 61 6b 65 20 74 68 65 6d |tly to m|ake them|
|00004330| 20 70 72 65 74 74 69 65 | 72 0d 09 2a 20 69 6e 20 | prettie|r..* in |
|00004340| 63 61 73 65 73 20 77 68 | 65 72 65 20 74 68 61 74 |cases wh|ere that|
|00004350| 20 63 61 6e 20 76 61 6c | 69 64 6c 79 20 62 65 20 | can val|idly be |
|00004360| 64 6f 6e 65 2e 0d 09 2a | 2f 0d 09 09 73 68 69 66 |done...*|/...shif|
|00004370| 74 5f 62 6f 75 6e 64 61 | 72 69 65 73 20 28 66 69 |t_bounda|ries (fi|
|00004380| 6c 65 30 50 74 72 2c 20 | 66 69 6c 65 31 50 74 72 |le0Ptr, |file1Ptr|
|00004390| 29 3b 0d 20 2f 2a 0d 09 | 2a 20 47 65 74 20 74 68 |);. /*..|* Get th|
|000043a0| 65 20 72 65 73 75 6c 74 | 73 20 6f 66 20 63 6f 6d |e result|s of com|
|000043b0| 70 61 72 69 73 6f 6e 20 | 69 6e 20 74 68 65 20 66 |parison |in the f|
|000043c0| 6f 72 6d 20 6f 66 20 61 | 20 63 68 61 69 6e 0d 09 |orm of a| chain..|
|000043d0| 2a 20 6f 66 20 60 73 74 | 72 75 63 74 20 63 68 61 |* of `st|ruct cha|
|000043e0| 6e 67 65 27 73 20 2d 2d | 20 61 6e 20 65 64 69 74 |nge's --| an edit|
|000043f0| 20 73 63 72 69 70 74 2e | 0d 09 2a 2f 0d 09 09 66 | script.|..*/...f|
|00004400| 69 6c 65 31 50 74 72 2d | 3e 73 63 72 69 70 74 50 |ile1Ptr-|>scriptP|
|00004410| 74 72 20 3d 20 62 75 69 | 6c 64 5f 73 63 72 69 70 |tr = bui|ld_scrip|
|00004420| 74 20 28 66 69 6c 65 30 | 50 74 72 2c 20 66 69 6c |t (file0|Ptr, fil|
|00004430| 65 31 50 74 72 29 3b 0d | 09 7d 0d 7d 0d 0d 2f 2a |e1Ptr);.|.}.}../*|
|00004440| 20 44 69 73 63 61 72 64 | 20 6c 69 6e 65 73 20 66 | Discard| lines f|
|00004450| 72 6f 6d 20 6f 6e 65 20 | 66 69 6c 65 20 74 68 61 |rom one |file tha|
|00004460| 74 20 68 61 76 65 20 6e | 6f 20 6d 61 74 63 68 65 |t have n|o matche|
|00004470| 73 20 69 6e 20 74 68 65 | 20 6f 74 68 65 72 20 66 |s in the| other f|
|00004480| 69 6c 65 2e 0d 0d 09 20 | 41 20 6c 69 6e 65 20 77 |ile.... |A line w|
|00004490| 68 69 63 68 20 69 73 20 | 64 69 73 63 61 72 64 65 |hich is |discarde|
|000044a0| 64 20 77 69 6c 6c 20 6e | 6f 74 20 62 65 20 63 6f |d will n|ot be co|
|000044b0| 6e 73 69 64 65 72 65 64 | 20 62 79 20 74 68 65 20 |nsidered| by the |
|000044c0| 61 63 74 75 61 6c 0d 09 | 20 63 6f 6d 70 61 72 69 |actual..| compari|
|000044d0| 73 6f 6e 20 61 6c 67 6f | 72 69 74 68 6d 3b 20 69 |son algo|rithm; i|
|000044e0| 74 20 77 69 6c 6c 20 62 | 65 20 61 73 20 69 66 20 |t will b|e as if |
|000044f0| 74 68 61 74 20 6c 69 6e | 65 20 77 65 72 65 20 6e |that lin|e were n|
|00004500| 6f 74 20 69 6e 20 74 68 | 65 20 66 69 6c 65 2e 0d |ot in th|e file..|
|00004510| 09 20 54 68 65 20 66 69 | 6c 65 27 73 20 60 72 65 |. The fi|le's `re|
|00004520| 61 6c 69 6e 64 65 78 65 | 73 27 20 74 61 62 6c 65 |alindexe|s' table|
|00004530| 20 6d 61 70 73 20 76 69 | 72 74 75 61 6c 20 6c 69 | maps vi|rtual li|
|00004540| 6e 65 20 6e 75 6d 62 65 | 72 73 0d 09 20 28 77 68 |ne numbe|rs.. (wh|
|00004550| 69 63 68 20 64 6f 6e 27 | 74 20 63 6f 75 6e 74 20 |ich don'|t count |
|00004560| 74 68 65 20 64 69 73 63 | 61 72 64 65 64 20 6c 69 |the disc|arded li|
|00004570| 6e 65 73 29 20 69 6e 74 | 6f 20 72 65 61 6c 20 6c |nes) int|o real l|
|00004580| 69 6e 65 20 6e 75 6d 62 | 65 72 73 3b 0d 09 20 74 |ine numb|ers;.. t|
|00004590| 68 69 73 20 69 73 20 68 | 6f 77 20 74 68 65 20 61 |his is h|ow the a|
|000045a0| 63 74 75 61 6c 20 63 6f | 6d 70 61 72 69 73 6f 6e |ctual co|mparison|
|000045b0| 20 61 6c 67 6f 72 69 74 | 68 6d 20 70 72 6f 64 75 | algorit|hm produ|
|000045c0| 63 65 73 20 72 65 73 75 | 6c 74 73 0d 09 20 74 68 |ces resu|lts.. th|
|000045d0| 61 74 20 61 72 65 20 63 | 6f 6d 70 72 65 68 65 6e |at are c|omprehen|
|000045e0| 73 69 62 6c 65 20 77 68 | 65 6e 20 74 68 65 20 64 |sible wh|en the d|
|000045f0| 69 73 63 61 72 64 65 64 | 20 6c 69 6e 65 73 20 61 |iscarded| lines a|
|00004600| 72 65 20 63 6f 75 6e 74 | 65 64 2e 0d 0d 09 20 57 |re count|ed.... W|
|00004610| 68 65 6e 20 77 65 20 64 | 69 73 63 61 72 64 20 61 |hen we d|iscard a|
|00004620| 20 6c 69 6e 65 2c 20 77 | 65 20 61 6c 73 6f 20 6d | line, w|e also m|
|00004630| 61 72 6b 20 69 74 20 61 | 73 20 61 20 64 65 6c 65 |ark it a|s a dele|
|00004640| 74 69 6f 6e 20 6f 72 20 | 69 6e 73 65 72 74 69 6f |tion or |insertio|
|00004650| 6e 0d 09 20 73 6f 20 74 | 68 61 74 20 69 74 20 77 |n.. so t|hat it w|
|00004660| 69 6c 6c 20 62 65 20 70 | 72 69 6e 74 65 64 20 69 |ill be p|rinted i|
|00004670| 6e 20 74 68 65 20 6f 75 | 74 70 75 74 2e 09 2a 2f |n the ou|tput..*/|
|00004680| 0d 0d 76 6f 69 64 0d 64 | 69 73 63 61 72 64 5f 63 |..void.d|iscard_c|
|00004690| 6f 6e 66 75 73 69 6e 67 | 5f 6c 69 6e 65 73 20 28 |onfusing|_lines (|
|000046a0| 72 65 67 69 73 74 65 72 | 20 73 74 72 75 63 74 20 |register| struct |
|000046b0| 66 69 6c 65 5f 64 61 74 | 61 20 2a 66 69 6c 65 30 |file_dat|a *file0|
|000046c0| 50 74 72 2c 20 72 65 67 | 69 73 74 65 72 20 73 74 |Ptr, reg|ister st|
|000046d0| 72 75 63 74 20 66 69 6c | 65 5f 64 61 74 61 20 2a |ruct fil|e_data *|
|000046e0| 66 69 6c 65 31 50 74 72 | 29 0d 7b 0d 09 63 68 61 |file1Ptr|).{..cha|
|000046f0| 72 09 09 09 09 09 09 09 | 09 20 2a 64 69 73 63 61 |r.......|. *disca|
|00004700| 72 64 65 64 5b 32 5d 3b | 0d 09 69 6e 74 20 09 09 |rded[2];|..int ..|
|00004710| 09 09 09 09 09 09 20 2a | 65 71 75 69 76 5f 63 6f |...... *|equiv_co|
|00004720| 75 6e 74 5b 32 5d 3b 0d | 09 73 74 72 75 63 74 20 |unt[2];.|.struct |
|00004730| 66 69 6c 65 5f 64 61 74 | 61 09 09 20 2a 66 69 6c |file_dat|a.. *fil|
|00004740| 65 50 74 72 3b 0d 09 75 | 6e 73 69 67 6e 65 64 09 |ePtr;..u|nsigned.|
|00004750| 09 09 09 09 09 09 69 6e | 74 20 66 2c 20 69 3b 0d |......in|t f, i;.|
|00004760| 0d 09 2f 2a 20 41 6c 6c | 6f 63 61 74 65 20 6f 75 |../* All|ocate ou|
|00004770| 72 20 72 65 73 75 6c 74 | 73 2e 09 2a 2f 0d 09 66 |r result|s..*/..f|
|00004780| 69 6c 65 50 74 72 20 3d | 20 66 69 6c 65 30 50 74 |ilePtr =| file0Pt|
|00004790| 72 3b 0d 09 66 6f 72 20 | 28 66 20 3d 20 30 3b 20 |r;..for |(f = 0; |
|000047a0| 66 20 3c 20 32 3b 20 66 | 2b 2b 29 20 7b 0d 09 09 |f < 2; f|++) {...|
|000047b0| 69 66 20 28 66 69 6c 65 | 50 74 72 2d 3e 75 6e 64 |if (file|Ptr->und|
|000047c0| 69 73 63 61 72 64 65 64 | 20 3d 3d 20 4e 55 4c 4c |iscarded| == NULL|
|000047d0| 29 0d 09 09 09 66 69 6c | 65 50 74 72 2d 3e 75 6e |)....fil|ePtr->un|
|000047e0| 64 69 73 63 61 72 64 65 | 64 20 3d 20 28 69 6e 74 |discarde|d = (int|
|000047f0| 20 2a 29 20 78 6d 61 6c | 6c 6f 63 20 28 66 69 6c | *) xmal|loc (fil|
|00004800| 65 50 74 72 2d 3e 62 75 | 66 66 65 72 65 64 5f 6c |ePtr->bu|ffered_l|
|00004810| 69 6e 65 73 20 2a 20 73 | 69 7a 65 6f 66 20 28 69 |ines * s|izeof (i|
|00004820| 6e 74 29 29 3b 0d 09 09 | 69 66 20 28 66 69 6c 65 |nt));...|if (file|
|00004830| 50 74 72 2d 3e 72 65 61 | 6c 69 6e 64 65 78 65 73 |Ptr->rea|lindexes|
|00004840| 20 3d 3d 20 4e 55 4c 4c | 29 0d 09 09 20 66 69 6c | == NULL|)... fil|
|00004850| 65 50 74 72 2d 3e 72 65 | 61 6c 69 6e 64 65 78 65 |ePtr->re|alindexe|
|00004860| 73 20 3d 20 28 69 6e 74 | 20 2a 29 20 78 6d 61 6c |s = (int| *) xmal|
|00004870| 6c 6f 63 20 28 66 69 6c | 65 50 74 72 2d 3e 62 75 |loc (fil|ePtr->bu|
|00004880| 66 66 65 72 65 64 5f 6c | 69 6e 65 73 20 2a 20 73 |ffered_l|ines * s|
|00004890| 69 7a 65 6f 66 20 28 69 | 6e 74 29 29 3b 0d 09 09 |izeof (i|nt));...|
|000048a0| 66 69 6c 65 50 74 72 20 | 3d 20 66 69 6c 65 31 50 |filePtr |= file1P|
|000048b0| 74 72 3b 0d 09 7d 0d 0d | 09 2f 2a 20 53 65 74 20 |tr;..}..|./* Set |
|000048c0| 75 70 20 65 71 75 69 76 | 5f 63 6f 75 6e 74 5b 46 |up equiv|_count[F|
|000048d0| 5d 5b 49 5d 20 61 73 20 | 74 68 65 20 6e 75 6d 62 |][I] as |the numb|
|000048e0| 65 72 20 6f 66 20 6c 69 | 6e 65 73 20 69 6e 20 66 |er of li|nes in f|
|000048f0| 69 6c 65 20 46 0d 09 09 | 20 74 68 61 74 20 66 61 |ile F...| that fa|
|00004900| 6c 6c 20 69 6e 20 65 71 | 75 69 76 61 6c 65 6e 63 |ll in eq|uivalenc|
|00004910| 65 20 63 6c 61 73 73 20 | 49 2e 09 2a 2f 0d 0d 09 |e class |I..*/...|
|00004920| 65 71 75 69 76 5f 63 6f | 75 6e 74 5b 30 5d 20 3d |equiv_co|unt[0] =|
|00004930| 20 28 69 6e 74 20 2a 29 | 20 78 6d 61 6c 6c 6f 63 | (int *)| xmalloc|
|00004940| 20 28 66 69 6c 65 30 50 | 74 72 2d 3e 65 71 75 69 | (file0P|tr->equi|
|00004950| 76 5f 6d 61 78 20 2a 20 | 73 69 7a 65 6f 66 20 28 |v_max * |sizeof (|
|00004960| 69 6e 74 29 29 3b 0d 09 | 62 7a 65 72 6f 20 28 65 |int));..|bzero (e|
|00004970| 71 75 69 76 5f 63 6f 75 | 6e 74 5b 30 5d 2c 20 66 |quiv_cou|nt[0], f|
|00004980| 69 6c 65 30 50 74 72 2d | 3e 65 71 75 69 76 5f 6d |ile0Ptr-|>equiv_m|
|00004990| 61 78 20 2a 20 73 69 7a | 65 6f 66 20 28 69 6e 74 |ax * siz|eof (int|
|000049a0| 29 29 3b 0d 09 65 71 75 | 69 76 5f 63 6f 75 6e 74 |));..equ|iv_count|
|000049b0| 5b 31 5d 20 3d 20 28 69 | 6e 74 20 2a 29 20 78 6d |[1] = (i|nt *) xm|
|000049c0| 61 6c 6c 6f 63 20 28 66 | 69 6c 65 31 50 74 72 2d |alloc (f|ile1Ptr-|
|000049d0| 3e 65 71 75 69 76 5f 6d | 61 78 20 2a 20 73 69 7a |>equiv_m|ax * siz|
|000049e0| 65 6f 66 20 28 69 6e 74 | 29 29 3b 0d 09 62 7a 65 |eof (int|));..bze|
|000049f0| 72 6f 20 28 65 71 75 69 | 76 5f 63 6f 75 6e 74 5b |ro (equi|v_count[|
|00004a00| 31 5d 2c 20 66 69 6c 65 | 31 50 74 72 2d 3e 65 71 |1], file|1Ptr->eq|
|00004a10| 75 69 76 5f 6d 61 78 20 | 2a 20 73 69 7a 65 6f 66 |uiv_max |* sizeof|
|00004a20| 20 28 69 6e 74 29 29 3b | 0d 0d 09 66 6f 72 20 28 | (int));|...for (|
|00004a30| 69 20 3d 20 30 3b 20 69 | 20 3c 20 66 69 6c 65 30 |i = 0; i| < file0|
|00004a40| 50 74 72 2d 3e 62 75 66 | 66 65 72 65 64 5f 6c 69 |Ptr->buf|fered_li|
|00004a50| 6e 65 73 3b 20 2b 2b 69 | 29 0d 09 09 2b 2b 65 71 |nes; ++i|)...++eq|
|00004a60| 75 69 76 5f 63 6f 75 6e | 74 5b 30 5d 5b 66 69 6c |uiv_coun|t[0][fil|
|00004a70| 65 30 50 74 72 2d 3e 65 | 71 75 69 76 73 5b 69 5d |e0Ptr->e|quivs[i]|
|00004a80| 5d 3b 0d 09 66 6f 72 20 | 28 69 20 3d 20 30 3b 20 |];..for |(i = 0; |
|00004a90| 69 20 3c 20 66 69 6c 65 | 31 50 74 72 2d 3e 62 75 |i < file|1Ptr->bu|
|00004aa0| 66 66 65 72 65 64 5f 6c | 69 6e 65 73 3b 20 2b 2b |ffered_l|ines; ++|
|00004ab0| 69 29 0d 09 09 2b 2b 65 | 71 75 69 76 5f 63 6f 75 |i)...++e|quiv_cou|
|00004ac0| 6e 74 5b 31 5d 5b 66 69 | 6c 65 31 50 74 72 2d 3e |nt[1][fi|le1Ptr->|
|00004ad0| 65 71 75 69 76 73 5b 69 | 5d 5d 3b 0d 0d 09 2f 2a |equivs[i|]];.../*|
|00004ae0| 20 53 65 74 20 75 70 20 | 74 61 62 6c 65 73 20 6f | Set up |tables o|
|00004af0| 66 20 77 68 69 63 68 20 | 6c 69 6e 65 73 20 61 72 |f which |lines ar|
|00004b00| 65 20 67 6f 69 6e 67 20 | 74 6f 20 62 65 20 64 69 |e going |to be di|
|00004b10| 73 63 61 72 64 65 64 2e | 09 2a 2f 0d 0d 09 64 69 |scarded.|.*/...di|
|00004b20| 73 63 61 72 64 65 64 5b | 30 5d 20 3d 20 28 63 68 |scarded[|0] = (ch|
|00004b30| 61 72 20 2a 29 20 78 6d | 61 6c 6c 6f 63 20 28 66 |ar *) xm|alloc (f|
|00004b40| 69 6c 65 30 50 74 72 2d | 3e 62 75 66 66 65 72 65 |ile0Ptr-|>buffere|
|00004b50| 64 5f 6c 69 6e 65 73 29 | 3b 0d 09 64 69 73 63 61 |d_lines)|;..disca|
|00004b60| 72 64 65 64 5b 31 5d 20 | 3d 20 28 63 68 61 72 20 |rded[1] |= (char |
|00004b70| 2a 29 20 78 6d 61 6c 6c | 6f 63 20 28 66 69 6c 65 |*) xmall|oc (file|
|00004b80| 31 50 74 72 2d 3e 62 75 | 66 66 65 72 65 64 5f 6c |1Ptr->bu|ffered_l|
|00004b90| 69 6e 65 73 29 3b 0d 09 | 62 7a 65 72 6f 20 28 64 |ines);..|bzero (d|
|00004ba0| 69 73 63 61 72 64 65 64 | 5b 30 5d 2c 20 66 69 6c |iscarded|[0], fil|
|00004bb0| 65 30 50 74 72 2d 3e 62 | 75 66 66 65 72 65 64 5f |e0Ptr->b|uffered_|
|00004bc0| 6c 69 6e 65 73 29 3b 0d | 09 62 7a 65 72 6f 20 28 |lines);.|.bzero (|
|00004bd0| 64 69 73 63 61 72 64 65 | 64 5b 31 5d 2c 20 66 69 |discarde|d[1], fi|
|00004be0| 6c 65 31 50 74 72 2d 3e | 62 75 66 66 65 72 65 64 |le1Ptr->|buffered|
|00004bf0| 5f 6c 69 6e 65 73 29 3b | 0d 0d 09 2f 2a 20 4d 61 |_lines);|.../* Ma|
|00004c00| 72 6b 20 74 6f 20 62 65 | 20 64 69 73 63 61 72 64 |rk to be| discard|
|00004c10| 65 64 20 65 61 63 68 20 | 6c 69 6e 65 20 74 68 61 |ed each |line tha|
|00004c20| 74 20 6d 61 74 63 68 65 | 73 20 6e 6f 20 6c 69 6e |t matche|s no lin|
|00004c30| 65 20 6f 66 20 74 68 65 | 20 6f 74 68 65 72 20 66 |e of the| other f|
|00004c40| 69 6c 65 2e 0d 09 09 20 | 49 66 20 61 20 6c 69 6e |ile.... |If a lin|
|00004c50| 65 20 6d 61 74 63 68 65 | 73 20 6d 61 6e 79 20 6c |e matche|s many l|
|00004c60| 69 6e 65 73 2c 20 6d 61 | 72 6b 20 69 74 20 61 73 |ines, ma|rk it as|
|00004c70| 20 70 72 6f 76 69 73 69 | 6f 6e 61 6c 6c 79 20 64 | provisi|onally d|
|00004c80| 69 73 63 61 72 64 61 62 | 6c 65 2e 09 2a 2f 0d 0d |iscardab|le..*/..|
|00004c90| 09 66 69 6c 65 50 74 72 | 20 3d 20 66 69 6c 65 30 |.filePtr| = file0|
|00004ca0| 50 74 72 3b 0d 09 66 6f | 72 20 28 66 20 3d 20 30 |Ptr;..fo|r (f = 0|
|00004cb0| 3b 20 66 20 3c 20 32 3b | 20 66 2b 2b 29 0d 09 09 |; f < 2;| f++)...|
|00004cc0| 7b 0d 09 09 09 75 6e 73 | 69 67 6e 65 64 20 69 6e |{....uns|igned in|
|00004cd0| 74 20 65 6e 64 20 3d 20 | 66 69 6c 65 50 74 72 2d |t end = |filePtr-|
|00004ce0| 3e 62 75 66 66 65 72 65 | 64 5f 6c 69 6e 65 73 3b |>buffere|d_lines;|
|00004cf0| 0d 09 09 09 63 68 61 72 | 20 2a 64 69 73 63 61 72 |....char| *discar|
|00004d00| 64 73 20 3d 20 64 69 73 | 63 61 72 64 65 64 5b 66 |ds = dis|carded[f|
|00004d10| 5d 3b 0d 09 09 09 69 6e | 74 20 2a 63 6f 75 6e 74 |];....in|t *count|
|00004d20| 73 20 3d 20 65 71 75 69 | 76 5f 63 6f 75 6e 74 5b |s = equi|v_count[|
|00004d30| 31 20 2d 20 66 5d 3b 0d | 09 09 09 69 6e 74 20 2a |1 - f];.|...int *|
|00004d40| 65 71 75 69 76 73 20 3d | 20 66 69 6c 65 50 74 72 |equivs =| filePtr|
|00004d50| 2d 3e 65 71 75 69 76 73 | 3b 0d 09 09 09 75 6e 73 |->equivs|;....uns|
|00004d60| 69 67 6e 65 64 20 69 6e | 74 20 6d 61 6e 79 20 3d |igned in|t many =|
|00004d70| 20 35 3b 0d 09 09 09 75 | 6e 73 69 67 6e 65 64 20 | 5;....u|nsigned |
|00004d80| 69 6e 74 20 74 65 6d 20 | 3d 20 65 6e 64 20 2f 20 |int tem |= end / |
|00004d90| 36 34 3b 0d 0d 09 09 09 | 2f 2a 20 4d 75 6c 74 69 |64;.....|/* Multi|
|00004da0| 70 6c 79 20 4d 41 4e 59 | 20 62 79 20 61 70 70 72 |ply MANY| by appr|
|00004db0| 6f 78 69 6d 61 74 65 20 | 73 71 75 61 72 65 20 72 |oximate |square r|
|00004dc0| 6f 6f 74 20 6f 66 20 6e | 75 6d 62 65 72 20 6f 66 |oot of n|umber of|
|00004dd0| 20 6c 69 6e 65 73 2e 0d | 09 09 09 09 20 54 68 61 | lines..|.... Tha|
|00004de0| 74 20 69 73 20 74 68 65 | 20 74 68 72 65 73 68 6f |t is the| thresho|
|00004df0| 6c 64 20 66 6f 72 20 70 | 72 6f 76 69 73 69 6f 6e |ld for p|rovision|
|00004e00| 61 6c 6c 79 20 64 69 73 | 63 61 72 64 61 62 6c 65 |ally dis|cardable|
|00004e10| 20 6c 69 6e 65 73 2e 20 | 20 2a 2f 0d 09 09 09 77 | lines. | */....w|
|00004e20| 68 69 6c 65 20 28 28 74 | 65 6d 20 3d 20 74 65 6d |hile ((t|em = tem|
|00004e30| 20 3e 3e 20 32 29 20 3e | 20 30 29 0d 09 09 09 09 | >> 2) >| 0).....|
|00004e40| 6d 61 6e 79 20 2a 3d 20 | 32 3b 0d 0d 09 09 09 66 |many *= |2;.....f|
|00004e50| 6f 72 20 28 69 20 3d 20 | 30 3b 20 69 20 3c 20 65 |or (i = |0; i < e|
|00004e60| 6e 64 3b 20 69 2b 2b 29 | 0d 09 09 09 09 7b 0d 09 |nd; i++)|.....{..|
|00004e70| 09 09 09 09 75 6e 73 69 | 67 6e 65 64 20 69 6e 74 |....unsi|gned int|
|00004e80| 20 6e 6d 61 74 63 68 3b | 0d 09 09 09 09 09 69 66 | nmatch;|......if|
|00004e90| 20 28 65 71 75 69 76 73 | 5b 69 5d 20 3d 3d 20 30 | (equivs|[i] == 0|
|00004ea0| 29 0d 09 09 09 09 09 09 | 63 6f 6e 74 69 6e 75 65 |).......|continue|
|00004eb0| 3b 0d 09 09 09 09 09 6e | 6d 61 74 63 68 20 3d 20 |;......n|match = |
|00004ec0| 63 6f 75 6e 74 73 5b 65 | 71 75 69 76 73 5b 69 5d |counts[e|quivs[i]|
|00004ed0| 5d 3b 0d 09 09 09 09 09 | 69 66 20 28 6e 6d 61 74 |];......|if (nmat|
|00004ee0| 63 68 20 3d 3d 20 30 29 | 0d 09 09 09 09 09 09 64 |ch == 0)|.......d|
|00004ef0| 69 73 63 61 72 64 73 5b | 69 5d 20 3d 20 31 3b 0d |iscards[|i] = 1;.|
|00004f00| 09 09 09 09 09 65 6c 73 | 65 20 69 66 20 28 6e 6d |.....els|e if (nm|
|00004f10| 61 74 63 68 20 3e 20 6d | 61 6e 79 29 0d 09 09 09 |atch > m|any)....|
|00004f20| 09 09 09 64 69 73 63 61 | 72 64 73 5b 69 5d 20 3d |...disca|rds[i] =|
|00004f30| 20 32 3b 0d 09 09 09 09 | 7d 0d 09 09 09 66 69 6c | 2;.....|}....fil|
|00004f40| 65 50 74 72 20 3d 20 66 | 69 6c 65 31 50 74 72 3b |ePtr = f|ile1Ptr;|
|00004f50| 0d 09 09 7d 0d 0d 09 2f | 2a 20 44 6f 6e 27 74 20 |...}.../|* Don't |
|00004f60| 72 65 61 6c 6c 79 20 64 | 69 73 63 61 72 64 20 74 |really d|iscard t|
|00004f70| 68 65 20 70 72 6f 76 69 | 73 69 6f 6e 61 6c 20 6c |he provi|sional l|
|00004f80| 69 6e 65 73 20 65 78 63 | 65 70 74 20 77 68 65 6e |ines exc|ept when|
|00004f90| 20 74 68 65 79 20 6f 63 | 63 75 72 0d 09 09 20 69 | they oc|cur... i|
|00004fa0| 6e 20 61 20 72 75 6e 20 | 6f 66 20 64 69 73 63 61 |n a run |of disca|
|00004fb0| 72 64 61 62 6c 65 73 2c | 20 77 69 74 68 20 6e 6f |rdables,| with no|
|00004fc0| 6e 70 72 6f 76 69 73 69 | 6f 6e 61 6c 73 20 61 74 |nprovisi|onals at|
|00004fd0| 20 74 68 65 20 62 65 67 | 69 6e 6e 69 6e 67 0d 09 | the beg|inning..|
|00004fe0| 09 20 61 6e 64 20 65 6e | 64 2e 20 20 2a 2f 0d 0d |. and en|d.  */..|
|00004ff0| 09 66 69 6c 65 50 74 72 | 20 3d 20 66 69 6c 65 30 |.filePtr| = file0|
|00005000| 50 74 72 3b 0d 09 66 6f | 72 20 28 66 20 3d 20 30 |Ptr;..fo|r (f = 0|
|00005010| 3b 20 66 20 3c 20 32 3b | 20 66 2b 2b 29 0d 09 09 |; f < 2;| f++)...|
|00005020| 7b 0d 09 09 09 75 6e 73 | 69 67 6e 65 64 20 69 6e |{....uns|igned in|
|00005030| 74 20 65 6e 64 20 3d 20 | 66 69 6c 65 50 74 72 2d |t end = |filePtr-|
|00005040| 3e 62 75 66 66 65 72 65 | 64 5f 6c 69 6e 65 73 3b |>buffere|d_lines;|
|00005050| 0d 09 09 09 72 65 67 69 | 73 74 65 72 20 63 68 61 |....regi|ster cha|
|00005060| 72 20 2a 64 69 73 63 61 | 72 64 73 20 3d 20 64 69 |r *disca|rds = di|
|00005070| 73 63 61 72 64 65 64 5b | 66 5d 3b 0d 0d 09 09 09 |scarded[|f];.....|
|00005080| 66 6f 72 20 28 69 20 3d | 20 30 3b 20 69 20 3c 20 |for (i =| 0; i < |
|00005090| 65 6e 64 3b 20 69 2b 2b | 29 0d 09 09 09 09 7b 0d |end; i++|).....{.|
|000050a0| 09 09 09 09 09 2f 2a 20 | 43 61 6e 63 65 6c 20 70 |...../* |Cancel p|
|000050b0| 72 6f 76 69 73 69 6f 6e | 61 6c 20 64 69 73 63 61 |rovision|al disca|
|000050c0| 72 64 73 20 6e 6f 74 20 | 69 6e 20 6d 69 64 64 6c |rds not |in middl|
|000050d0| 65 20 6f 66 20 72 75 6e | 20 6f 66 20 64 69 73 63 |e of run| of disc|
|000050e0| 61 72 64 73 2e 09 2a 2f | 0d 09 09 09 09 09 69 66 |ards..*/|......if|
|000050f0| 20 28 64 69 73 63 61 72 | 64 73 5b 69 5d 20 3d 3d | (discar|ds[i] ==|
|00005100| 20 32 29 0d 09 09 09 09 | 09 09 64 69 73 63 61 72 | 2).....|..discar|
|00005110| 64 73 5b 69 5d 20 3d 20 | 30 3b 0d 09 09 09 09 09 |ds[i] = |0;......|
|00005120| 65 6c 73 65 20 69 66 20 | 28 64 69 73 63 61 72 64 |else if |(discard|
|00005130| 73 5b 69 5d 20 21 3d 20 | 30 29 0d 09 09 09 09 09 |s[i] != |0)......|
|00005140| 09 7b 0d 09 09 09 09 09 | 09 09 2f 2a 20 57 65 20 |.{......|../* We |
|00005150| 68 61 76 65 20 66 6f 75 | 6e 64 20 61 20 6e 6f 6e |have fou|nd a non|
|00005160| 70 72 6f 76 69 73 69 6f | 6e 61 6c 20 64 69 73 63 |provisio|nal disc|
|00005170| 61 72 64 2e 09 2a 2f 0d | 09 09 09 09 09 09 09 72 |ard..*/.|.......r|
|00005180| 65 67 69 73 74 65 72 20 | 75 6e 73 69 67 6e 65 64 |egister |unsigned|
|00005190| 20 69 6e 74 20 6a 3b 0d | 09 09 09 09 09 09 09 75 | int j;.|.......u|
|000051a0| 6e 73 69 67 6e 65 64 20 | 69 6e 74 20 6c 65 6e 67 |nsigned |int leng|
|000051b0| 74 68 3b 0d 09 09 09 09 | 09 09 09 75 6e 73 69 67 |th;.....|...unsig|
|000051c0| 6e 65 64 20 69 6e 74 20 | 70 72 6f 76 69 73 69 6f |ned int |provisio|
|000051d0| 6e 61 6c 20 3d 20 30 3b | 0d 0d 09 09 09 09 09 09 |nal = 0;|........|
|000051e0| 09 2f 2a 20 46 69 6e 64 | 20 65 6e 64 20 6f 66 20 |./* Find| end of |
|000051f0| 74 68 69 73 20 72 75 6e | 20 6f 66 20 64 69 73 63 |this run| of disc|
|00005200| 61 72 64 61 62 6c 65 20 | 6c 69 6e 65 73 2e 0d 09 |ardable |lines...|
|00005210| 09 09 09 09 09 09 09 20 | 43 6f 75 6e 74 20 68 6f |....... |Count ho|
|00005220| 77 20 6d 61 6e 79 20 61 | 72 65 20 70 72 6f 76 69 |w many a|re provi|
|00005230| 73 69 6f 6e 61 6c 6c 79 | 20 64 69 73 63 61 72 64 |sionally| discard|
|00005240| 61 62 6c 65 2e 09 2a 2f | 0d 09 09 09 09 09 09 09 |able..*/|........|
|00005250| 66 6f 72 20 28 6a 20 3d | 20 69 3b 20 6a 20 3c 20 |for (j =| i; j < |
|00005260| 65 6e 64 3b 20 6a 2b 2b | 29 0d 09 09 09 09 09 09 |end; j++|).......|
|00005270| 09 09 7b 0d 09 09 09 09 | 09 09 09 09 09 69 66 20 |..{.....|.....if |
|00005280| 28 64 69 73 63 61 72 64 | 73 5b 6a 5d 20 3d 3d 20 |(discard|s[j] == |
|00005290| 30 29 0d 09 09 09 09 09 | 09 09 09 09 09 62 72 65 |0)......|.....bre|
|000052a0| 61 6b 3b 0d 09 09 09 09 | 09 09 09 09 09 69 66 20 |ak;.....|.....if |
|000052b0| 28 64 69 73 63 61 72 64 | 73 5b 6a 5d 20 3d 3d 20 |(discard|s[j] == |
|000052c0| 32 29 0d 09 09 09 09 09 | 09 09 09 09 09 2b 2b 70 |2)......|.....++p|
|000052d0| 72 6f 76 69 73 69 6f 6e | 61 6c 3b 0d 09 09 09 09 |rovision|al;.....|
|000052e0| 09 09 09 09 7d 0d 0d 09 | 09 09 09 09 09 09 2f 2a |....}...|....../*|
|000052f0| 20 43 61 6e 63 65 6c 20 | 70 72 6f 76 69 73 69 6f | Cancel |provisio|
|00005300| 6e 61 6c 20 64 69 73 63 | 61 72 64 73 20 61 74 20 |nal disc|ards at |
|00005310| 65 6e 64 2c 20 61 6e 64 | 20 73 68 72 69 6e 6b 20 |end, and| shrink |
|00005320| 74 68 65 20 72 75 6e 2e | 09 2a 2f 0d 09 09 09 09 |the run.|.*/.....|
|00005330| 09 09 09 77 68 69 6c 65 | 20 28 6a 20 3e 20 69 20 |...while| (j > i |
|00005340| 26 26 20 64 69 73 63 61 | 72 64 73 5b 6a 20 2d 20 |&& disca|rds[j - |
|00005350| 31 5d 20 3d 3d 20 32 29 | 0d 09 09 09 09 09 09 09 |1] == 2)|........|
|00005360| 09 64 69 73 63 61 72 64 | 73 5b 2d 2d 6a 5d 20 3d |.discard|s[--j] =|
|00005370| 20 30 2c 20 2d 2d 70 72 | 6f 76 69 73 69 6f 6e 61 | 0, --pr|ovisiona|
|00005380| 6c 3b 0d 0d 09 09 09 09 | 09 09 09 2f 2a 20 4e 6f |l;......|.../* No|
|00005390| 77 20 77 65 20 68 61 76 | 65 20 74 68 65 20 6c 65 |w we hav|e the le|
|000053a0| 6e 67 74 68 20 6f 66 20 | 61 20 72 75 6e 20 6f 66 |ngth of |a run of|
|000053b0| 20 64 69 73 63 61 72 64 | 61 62 6c 65 20 6c 69 6e | discard|able lin|
|000053c0| 65 73 0d 09 09 09 09 09 | 09 09 09 20 77 68 6f 73 |es......|... whos|
|000053d0| 65 20 66 69 72 73 74 20 | 61 6e 64 20 6c 61 73 74 |e first |and last|
|000053e0| 20 61 72 65 20 6e 6f 74 | 20 70 72 6f 76 69 73 69 | are not| provisi|
|000053f0| 6f 6e 61 6c 2e 09 2a 2f | 0d 09 09 09 09 09 09 09 |onal..*/|........|
|00005400| 6c 65 6e 67 74 68 20 3d | 20 6a 20 2d 20 69 3b 0d |length =| j - i;.|
|00005410| 0d 09 09 09 09 09 09 09 | 2f 2a 20 49 66 20 31 2f |........|/* If 1/|
|00005420| 34 20 6f 66 20 74 68 65 | 20 6c 69 6e 65 73 20 69 |4 of the| lines i|
|00005430| 6e 20 74 68 65 20 72 75 | 6e 20 61 72 65 20 70 72 |n the ru|n are pr|
|00005440| 6f 76 69 73 69 6f 6e 61 | 6c 2c 0d 09 09 09 09 09 |ovisiona|l,......|
|00005450| 09 09 09 20 63 61 6e 63 | 65 6c 20 64 69 73 63 61 |... canc|el disca|
|00005460| 72 64 69 6e 67 20 6f 66 | 20 61 6c 6c 20 70 72 6f |rding of| all pro|
|00005470| 76 69 73 69 6f 6e 61 6c | 20 6c 69 6e 65 73 20 69 |visional| lines i|
|00005480| 6e 20 74 68 65 20 72 75 | 6e 2e 20 20 2a 2f 0d 09 |n the ru|n.  */..|
|00005490| 09 09 09 09 09 09 69 66 | 20 28 70 72 6f 76 69 73 |......if| (provis|
|000054a0| 69 6f 6e 61 6c 20 2a 20 | 34 20 3e 20 6c 65 6e 67 |ional * |4 > leng|
|000054b0| 74 68 29 0d 09 09 09 09 | 09 09 09 09 7b 0d 09 09 |th).....|....{...|
|000054c0| 09 09 09 09 09 09 09 77 | 68 69 6c 65 20 28 6a 20 |.......w|hile (j |
|000054d0| 3e 20 69 29 0d 09 09 09 | 09 09 09 09 09 09 09 69 |> i)....|.......i|
|000054e0| 66 20 28 64 69 73 63 61 | 72 64 73 5b 2d 2d 6a 5d |f (disca|rds[--j]|
|000054f0| 20 3d 3d 20 32 29 0d 09 | 09 09 09 09 09 09 09 09 | == 2)..|........|
|00005500| 09 09 64 69 73 63 61 72 | 64 73 5b 6a 5d 20 3d 20 |..discar|ds[j] = |
|00005510| 30 3b 0d 09 09 09 09 09 | 09 09 09 7d 0d 09 09 09 |0;......|...}....|
|00005520| 09 09 09 09 65 6c 73 65 | 0d 09 09 09 09 09 09 09 |....else|........|
|00005530| 09 7b 0d 09 09 09 09 09 | 09 09 09 09 72 65 67 69 |.{......|....regi|
|00005540| 73 74 65 72 20 75 6e 73 | 69 67 6e 65 64 20 69 6e |ster uns|igned in|
|00005550| 74 20 63 6f 6e 73 65 63 | 3b 0d 09 09 09 09 09 09 |t consec|;.......|
|00005560| 09 09 09 75 6e 73 69 67 | 6e 65 64 20 69 6e 74 20 |...unsig|ned int |
|00005570| 6d 69 6e 69 6d 75 6d 20 | 3d 20 31 3b 0d 09 09 09 |minimum |= 1;....|
|00005580| 09 09 09 09 09 09 75 6e | 73 69 67 6e 65 64 20 69 |......un|signed i|
|00005590| 6e 74 20 74 65 6d 20 3d | 20 6c 65 6e 67 74 68 20 |nt tem =| length |
|000055a0| 2f 20 34 3b 0d 0d 09 09 | 09 09 09 09 09 09 09 2f |/ 4;....|......./|
|000055b0| 2a 20 4d 49 4e 49 4d 55 | 4d 20 69 73 20 61 70 70 |* MINIMU|M is app|
|000055c0| 72 6f 78 69 6d 61 74 65 | 20 73 71 75 61 72 65 20 |roximate| square |
|000055d0| 72 6f 6f 74 20 6f 66 20 | 4c 45 4e 47 54 48 2f 34 |root of |LENGTH/4|
|000055e0| 2e 0d 09 09 09 09 09 09 | 09 09 09 09 20 41 20 73 |........|.... A s|
|000055f0| 75 62 72 75 6e 20 6f 66 | 20 74 77 6f 20 6f 72 20 |ubrun of| two or |
|00005600| 6d 6f 72 65 20 70 72 6f | 76 69 73 69 6f 6e 61 6c |more pro|visional|
|00005610| 73 20 63 61 6e 20 73 74 | 61 6e 64 0d 09 09 09 09 |s can st|and.....|
|00005620| 09 09 09 09 09 09 20 77 | 68 65 6e 20 4c 45 4e 47 |...... w|hen LENG|
|00005630| 54 48 20 69 73 20 61 74 | 20 6c 65 61 73 74 20 31 |TH is at| least 1|
|00005640| 36 2e 0d 09 09 09 09 09 | 09 09 09 09 09 20 41 20 |6.......|..... A |
|00005650| 73 75 62 72 75 6e 20 6f | 66 20 34 20 6f 72 20 6d |subrun o|f 4 or m|
|00005660| 6f 72 65 20 63 61 6e 20 | 73 74 61 6e 64 20 77 68 |ore can |stand wh|
|00005670| 65 6e 20 4c 45 4e 47 54 | 48 20 3e 3d 20 36 34 2e |en LENGT|H >= 64.|
|00005680| 20 20 2a 2f 0d 09 09 09 | 09 09 09 09 09 09 77 68 |  */....|......wh|
|00005690| 69 6c 65 20 28 28 74 65 | 6d 20 3d 20 74 65 6d 20 |ile ((te|m = tem |
|000056a0| 3e 3e 20 32 29 20 3e 20 | 30 29 0d 09 09 09 09 09 |>> 2) > |0)......|
|000056b0| 09 09 09 09 09 6d 69 6e | 69 6d 75 6d 20 2a 3d 20 |.....min|imum *= |
|000056c0| 32 3b 0d 09 09 09 09 09 | 09 09 09 09 6d 69 6e 69 |2;......|....mini|
|000056d0| 6d 75 6d 2b 2b 3b 0d 0d | 09 09 09 09 09 09 09 09 |mum++;..|........|
|000056e0| 09 2f 2a 20 43 61 6e 63 | 65 6c 20 61 6e 79 20 73 |./* Canc|el any s|
|000056f0| 75 62 72 75 6e 20 6f 66 | 20 4d 49 4e 49 4d 55 4d |ubrun of| MINIMUM|
|00005700| 20 6f 72 20 6d 6f 72 65 | 20 70 72 6f 76 69 73 69 | or more| provisi|
|00005710| 6f 6e 61 6c 73 0d 09 09 | 09 09 09 09 09 09 09 09 |onals...|........|
|00005720| 20 77 69 74 68 69 6e 20 | 74 68 65 20 6c 61 72 67 | within |the larg|
|00005730| 65 72 20 72 75 6e 2e 20 | 20 2a 2f 0d 09 09 09 09 |er run. | */.....|
|00005740| 09 09 09 09 09 66 6f 72 | 20 28 6a 20 3d 20 30 2c |.....for| (j = 0,|
|00005750| 20 63 6f 6e 73 65 63 20 | 3d 20 30 3b 20 6a 20 3c | consec |= 0; j <|
|00005760| 20 6c 65 6e 67 74 68 3b | 20 6a 2b 2b 29 0d 09 09 | length;| j++)...|
|00005770| 09 09 09 09 09 09 09 09 | 69 66 20 28 64 69 73 63 |........|if (disc|
|00005780| 61 72 64 73 5b 69 20 2b | 20 6a 5d 20 21 3d 20 32 |ards[i +| j] != 2|
|00005790| 29 0d 09 09 09 09 09 09 | 09 09 09 09 09 63 6f 6e |).......|.....con|
|000057a0| 73 65 63 20 3d 20 30 3b | 0d 09 09 09 09 09 09 09 |sec = 0;|........|
|000057b0| 09 09 09 65 6c 73 65 20 | 69 66 20 28 6d 69 6e 69 |...else |if (mini|
|000057c0| 6d 75 6d 20 3d 3d 20 2b | 2b 63 6f 6e 73 65 63 29 |mum == +|+consec)|
|000057d0| 0d 09 09 09 09 09 09 09 | 09 09 09 09 2f 2a 20 42 |........|..../* B|
|000057e0| 61 63 6b 20 75 70 20 74 | 6f 20 73 74 61 72 74 20 |ack up t|o start |
|000057f0| 6f 66 20 73 75 62 72 75 | 6e 2c 20 74 6f 20 63 61 |of subru|n, to ca|
|00005800| 6e 63 65 6c 20 69 74 20 | 61 6c 6c 2e 09 2a 2f 0d |ncel it |all..*/.|
|00005810| 09 09 09 09 09 09 09 09 | 09 09 09 6a 20 2d 3d 20 |........|...j -= |
|00005820| 63 6f 6e 73 65 63 3b 0d | 09 09 09 09 09 09 09 09 |consec;.|........|
|00005830| 09 09 65 6c 73 65 20 69 | 66 20 28 6d 69 6e 69 6d |..else i|f (minim|
|00005840| 75 6d 20 3c 20 63 6f 6e | 73 65 63 29 0d 09 09 09 |um < con|sec)....|
|00005850| 09 09 09 09 09 09 09 09 | 64 69 73 63 61 72 64 73 |........|discards|
|00005860| 5b 69 20 2b 20 6a 5d 20 | 3d 20 30 3b 0d 0d 09 09 |[i + j] |= 0;....|
|00005870| 09 09 09 09 09 09 09 2f | 2a 20 53 63 61 6e 20 66 |......./|* Scan f|
|00005880| 72 6f 6d 20 62 65 67 69 | 6e 6e 69 6e 67 20 6f 66 |rom begi|nning of|
|00005890| 20 72 75 6e 0d 09 09 09 | 09 09 09 09 09 09 09 20 | run....|....... |
|000058a0| 75 6e 74 69 6c 20 77 65 | 20 66 69 6e 64 20 33 20 |until we| find 3 |
|000058b0| 6f 72 20 6d 6f 72 65 20 | 6e 6f 6e 70 72 6f 76 69 |or more |nonprovi|
|000058c0| 73 69 6f 6e 61 6c 73 20 | 69 6e 20 61 20 72 6f 77 |sionals |in a row|
|000058d0| 0d 09 09 09 09 09 09 09 | 09 09 09 20 6f 72 20 75 |........|... or u|
|000058e0| 6e 74 69 6c 20 74 68 65 | 20 66 69 72 73 74 20 6e |ntil the| first n|
|000058f0| 6f 6e 70 72 6f 76 69 73 | 69 6f 6e 61 6c 20 61 74 |onprovis|ional at|
|00005900| 20 6c 65 61 73 74 20 38 | 20 6c 69 6e 65 73 20 69 | least 8| lines i|
|00005910| 6e 2e 0d 09 09 09 09 09 | 09 09 09 09 09 20 55 6e |n.......|..... Un|
|00005920| 74 69 6c 20 74 68 61 74 | 20 70 6f 69 6e 74 2c 20 |til that| point, |
|00005930| 63 61 6e 63 65 6c 20 61 | 6e 79 20 70 72 6f 76 69 |cancel a|ny provi|
|00005940| 73 69 6f 6e 61 6c 73 2e | 20 20 2a 2f 0d 09 09 09 |sionals.|  */....|
|00005950| 09 09 09 09 09 09 66 6f | 72 20 28 6a 20 3d 20 30 |......fo|r (j = 0|
|00005960| 2c 20 63 6f 6e 73 65 63 | 20 3d 20 30 3b 20 6a 20 |, consec| = 0; j |
|00005970| 3c 20 6c 65 6e 67 74 68 | 3b 20 6a 2b 2b 29 0d 09 |< length|; j++)..|
|00005980| 09 09 09 09 09 09 09 09 | 09 7b 0d 09 09 09 09 09 |........|.{......|
|00005990| 09 09 09 09 09 09 69 66 | 20 28 6a 20 3e 3d 20 38 |......if| (j >= 8|
|000059a0| 20 26 26 20 64 69 73 63 | 61 72 64 73 5b 69 20 2b | && disc|ards[i +|
|000059b0| 20 6a 5d 20 3d 3d 20 31 | 29 0d 09 09 09 09 09 09 | j] == 1|).......|
|000059c0| 09 09 09 09 09 09 62 72 | 65 61 6b 3b 0d 09 09 09 |......br|eak;....|
|000059d0| 09 09 09 09 09 09 09 09 | 69 66 20 28 64 69 73 63 |........|if (disc|
|000059e0| 61 72 64 73 5b 69 20 2b | 20 6a 5d 20 3d 3d 20 32 |ards[i +| j] == 2|
|000059f0| 29 0d 09 09 09 09 09 09 | 09 09 09 09 09 09 63 6f |).......|......co|
|00005a00| 6e 73 65 63 20 3d 20 30 | 2c 20 64 69 73 63 61 72 |nsec = 0|, discar|
|00005a10| 64 73 5b 69 20 2b 20 6a | 5d 20 3d 20 30 3b 0d 09 |ds[i + j|] = 0;..|
|00005a20| 09 09 09 09 09 09 09 09 | 09 09 65 6c 73 65 20 69 |........|..else i|
|00005a30| 66 20 28 64 69 73 63 61 | 72 64 73 5b 69 20 2b 20 |f (disca|rds[i + |
|00005a40| 6a 5d 20 3d 3d 20 30 29 | 0d 09 09 09 09 09 09 09 |j] == 0)|........|
|00005a50| 09 09 09 09 09 63 6f 6e | 73 65 63 20 3d 20 30 3b |.....con|sec = 0;|
|00005a60| 0d 09 09 09 09 09 09 09 | 09 09 09 09 65 6c 73 65 |........|....else|
|00005a70| 0d 09 09 09 09 09 09 09 | 09 09 09 09 09 63 6f 6e |........|.....con|
|00005a80| 73 65 63 2b 2b 3b 0d 09 | 09 09 09 09 09 09 09 09 |sec++;..|........|
|00005a90| 09 09 69 66 20 28 63 6f | 6e 73 65 63 20 3d 3d 20 |..if (co|nsec == |
|00005aa0| 33 29 0d 09 09 09 09 09 | 09 09 09 09 09 09 09 62 |3)......|.......b|
|00005ab0| 72 65 61 6b 3b 0d 09 09 | 09 09 09 09 09 09 09 09 |reak;...|........|
|00005ac0| 7d 0d 0d 09 09 09 09 09 | 09 09 09 09 2f 2a 20 49 |}.......|..../* I|
|00005ad0| 20 61 64 76 61 6e 63 65 | 73 20 74 6f 20 74 68 65 | advance|s to the|
|00005ae0| 20 6c 61 73 74 20 6c 69 | 6e 65 20 6f 66 20 74 68 | last li|ne of th|
|00005af0| 65 20 72 75 6e 2e 09 2a | 2f 0d 09 09 09 09 09 09 |e run..*|/.......|
|00005b00| 09 09 09 69 20 2b 3d 20 | 6c 65 6e 67 74 68 20 2d |...i += |length -|
|00005b10| 20 31 3b 0d 0d 09 09 09 | 09 09 09 09 09 09 2f 2a | 1;.....|....../*|
|00005b20| 20 53 61 6d 65 20 74 68 | 69 6e 67 2c 20 66 72 6f | Same th|ing, fro|
|00005b30| 6d 20 65 6e 64 2e 09 2a | 2f 0d 09 09 09 09 09 09 |m end..*|/.......|
|00005b40| 09 09 09 66 6f 72 20 28 | 6a 20 3d 20 30 2c 20 63 |...for (|j = 0, c|
|00005b50| 6f 6e 73 65 63 20 3d 20 | 30 3b 20 6a 20 3c 20 6c |onsec = |0; j < l|
|00005b60| 65 6e 67 74 68 3b 20 6a | 2b 2b 29 0d 09 09 09 09 |ength; j|++).....|
|00005b70| 09 09 09 09 09 09 7b 0d | 09 09 09 09 09 09 09 09 |......{.|........|
|00005b80| 09 09 09 69 66 20 28 6a | 20 3e 3d 20 38 20 26 26 |...if (j| >= 8 &&|
|00005b90| 20 64 69 73 63 61 72 64 | 73 5b 69 20 2d 20 6a 5d | discard|s[i - j]|
|00005ba0| 20 3d 3d 20 31 29 0d 09 | 09 09 09 09 09 09 09 09 | == 1)..|........|
|00005bb0| 09 09 09 62 72 65 61 6b | 3b 0d 09 09 09 09 09 09 |...break|;.......|
|00005bc0| 09 09 09 09 09 69 66 20 | 28 64 69 73 63 61 72 64 |.....if |(discard|
|00005bd0| 73 5b 69 20 2d 20 6a 5d | 20 3d 3d 20 32 29 0d 09 |s[i - j]| == 2)..|
|00005be0| 09 09 09 09 09 09 09 09 | 09 09 09 63 6f 6e 73 65 |........|...conse|
|00005bf0| 63 20 3d 20 30 2c 20 64 | 69 73 63 61 72 64 73 5b |c = 0, d|iscards[|
|00005c00| 69 20 2d 20 6a 5d 20 3d | 20 30 3b 0d 09 09 09 09 |i - j] =| 0;.....|
|00005c10| 09 09 09 09 09 09 09 65 | 6c 73 65 20 69 66 20 28 |.......e|lse if (|
|00005c20| 64 69 73 63 61 72 64 73 | 5b 69 20 2d 20 6a 5d 20 |discards|[i - j] |
|00005c30| 3d 3d 20 30 29 0d 09 09 | 09 09 09 09 09 09 09 09 |== 0)...|........|
|00005c40| 09 09 63 6f 6e 73 65 63 | 20 3d 20 30 3b 0d 09 09 |..consec| = 0;...|
|00005c50| 09 09 09 09 09 09 09 09 | 09 65 6c 73 65 0d 09 09 |........|.else...|
|00005c60| 09 09 09 09 09 09 09 09 | 09 09 63 6f 6e 73 65 63 |........|..consec|
|00005c70| 2b 2b 3b 0d 09 09 09 09 | 09 09 09 09 09 09 09 69 |++;.....|.......i|
|00005c80| 66 20 28 63 6f 6e 73 65 | 63 20 3d 3d 20 33 29 0d |f (conse|c == 3).|
|00005c90| 09 09 09 09 09 09 09 09 | 09 09 09 09 62 72 65 61 |........|....brea|
|00005ca0| 6b 3b 0d 09 09 09 09 09 | 09 09 09 09 09 7d 0d 09 |k;......|.....}..|
|00005cb0| 09 09 09 09 09 09 09 7d | 0d 09 09 09 09 09 09 7d |.......}|.......}|
|00005cc0| 0d 09 09 09 09 7d 0d 09 | 09 09 66 69 6c 65 50 74 |.....}..|..filePt|
|00005cd0| 72 20 3d 20 66 69 6c 65 | 31 50 74 72 3b 0d 09 09 |r = file|1Ptr;...|
|00005ce0| 7d 0d 0d 09 2f 2a 20 41 | 63 74 75 61 6c 6c 79 20 |}.../* A|ctually |
|00005cf0| 64 69 73 63 61 72 64 20 | 74 68 65 20 6c 69 6e 65 |discard |the line|
|00005d00| 73 2e 20 2a 2f 0d 09 66 | 69 6c 65 50 74 72 20 3d |s. */..f|ilePtr =|
|00005d10| 20 66 69 6c 65 30 50 74 | 72 3b 0d 09 66 6f 72 20 | file0Pt|r;..for |
|00005d20| 28 66 20 3d 20 30 3b 20 | 66 20 3c 20 32 3b 20 66 |(f = 0; |f < 2; f|
|00005d30| 2b 2b 29 0d 09 09 7b 0d | 09 09 09 63 68 61 72 20 |++)...{.|...char |
|00005d40| 2a 64 69 73 63 61 72 64 | 73 20 3d 20 64 69 73 63 |*discard|s = disc|
|00005d50| 61 72 64 65 64 5b 66 5d | 3b 0d 09 09 09 75 6e 73 |arded[f]|;....uns|
|00005d60| 69 67 6e 65 64 20 69 6e | 74 20 65 6e 64 20 3d 20 |igned in|t end = |
|00005d70| 66 69 6c 65 50 74 72 2d | 3e 62 75 66 66 65 72 65 |filePtr-|>buffere|
|00005d80| 64 5f 6c 69 6e 65 73 3b | 0d 09 09 09 75 6e 73 69 |d_lines;|....unsi|
|00005d90| 67 6e 65 64 20 69 6e 74 | 20 6a 20 3d 20 30 3b 0d |gned int| j = 0;.|
|00005da0| 09 09 09 66 6f 72 20 28 | 69 20 3d 20 30 3b 20 69 |...for (|i = 0; i|
|00005db0| 20 3c 20 65 6e 64 3b 20 | 2b 2b 69 29 0d 09 09 09 | < end; |++i)....|
|00005dc0| 09 69 66 20 28 64 69 73 | 63 61 72 64 73 5b 69 5d |.if (dis|cards[i]|
|00005dd0| 20 3d 3d 20 30 29 0d 09 | 09 09 09 09 7b 0d 09 09 | == 0)..|....{...|
|00005de0| 09 09 09 09 66 69 6c 65 | 50 74 72 2d 3e 75 6e 64 |....file|Ptr->und|
|00005df0| 69 73 63 61 72 64 65 64 | 5b 6a 5d 20 3d 20 66 69 |iscarded|[j] = fi|
|00005e00| 6c 65 50 74 72 2d 3e 65 | 71 75 69 76 73 5b 69 5d |lePtr->e|quivs[i]|
|00005e10| 3b 0d 09 09 09 09 09 09 | 66 69 6c 65 50 74 72 2d |;.......|filePtr-|
|00005e20| 3e 72 65 61 6c 69 6e 64 | 65 78 65 73 5b 6a 2b 2b |>realind|exes[j++|
|00005e30| 5d 20 3d 20 69 3b 0d 09 | 09 09 09 09 7d 0d 09 09 |] = i;..|....}...|
|00005e40| 09 09 65 6c 73 65 0d 09 | 09 09 09 09 66 69 6c 65 |..else..|....file|
|00005e50| 50 74 72 2d 3e 63 68 61 | 6e 67 65 64 5f 66 6c 61 |Ptr->cha|nged_fla|
|00005e60| 67 5b 69 5d 20 3d 20 31 | 3b 0d 09 09 09 66 69 6c |g[i] = 1|;....fil|
|00005e70| 65 50 74 72 2d 3e 6e 6f | 6e 64 69 73 63 61 72 64 |ePtr->no|ndiscard|
|00005e80| 65 64 5f 6c 69 6e 65 73 | 20 3d 20 6a 3b 0d 09 09 |ed_lines| = j;...|
|00005e90| 09 66 69 6c 65 50 74 72 | 20 3d 20 66 69 6c 65 31 |.filePtr| = file1|
|00005ea0| 50 74 72 3b 0d 09 09 7d | 0d 0d 09 66 72 65 65 20 |Ptr;...}|...free |
|00005eb0| 28 64 69 73 63 61 72 64 | 65 64 5b 31 5d 29 3b 0d |(discard|ed[1]);.|
|00005ec0| 09 66 72 65 65 20 28 64 | 69 73 63 61 72 64 65 64 |.free (d|iscarded|
|00005ed0| 5b 30 5d 29 3b 0d 09 66 | 72 65 65 20 28 65 71 75 |[0]);..f|ree (equ|
|00005ee0| 69 76 5f 63 6f 75 6e 74 | 5b 31 5d 29 3b 0d 09 66 |iv_count|[1]);..f|
|00005ef0| 72 65 65 20 28 65 71 75 | 69 76 5f 63 6f 75 6e 74 |ree (equ|iv_count|
|00005f00| 5b 30 5d 29 3b 0d 7d 0d | 0d 76 6f 69 64 20 66 72 |[0]);.}.|.void fr|
|00005f10| 65 65 46 69 6c 65 20 28 | 72 65 67 69 73 74 65 72 |eeFile (|register|
|00005f20| 20 73 74 72 75 63 74 20 | 66 69 6c 65 5f 64 61 74 | struct |file_dat|
|00005f30| 61 20 2a 66 69 6c 65 50 | 74 72 29 0d 7b 0d 09 73 |a *fileP|tr).{..s|
|00005f40| 74 72 75 63 74 20 63 68 | 61 6e 67 65 20 2a 6e 65 |truct ch|ange *ne|
|00005f50| 78 74 53 63 72 69 70 74 | 50 74 72 3b 0d 09 73 74 |xtScript|Ptr;..st|
|00005f60| 72 75 63 74 20 63 68 61 | 6e 67 65 20 2a 73 63 72 |ruct cha|nge *scr|
|00005f70| 69 70 74 50 74 72 3b 0d | 0d 20 20 69 66 20 28 66 |iptPtr;.|.  if (f|
|00005f80| 69 6c 65 50 74 72 2d 3e | 64 65 73 63 20 21 3d 20 |ilePtr->|desc != |
|00005f90| 4e 55 4c 4c 29 20 7b 0d | 09 09 66 63 6c 6f 73 65 |NULL) {.|..fclose|
|00005fa0| 20 28 66 69 6c 65 50 74 | 72 2d 3e 64 65 73 63 29 | (filePt|r->desc)|
|00005fb0| 3b 0d 09 09 66 69 6c 65 | 50 74 72 2d 3e 64 65 73 |;...file|Ptr->des|
|00005fc0| 63 20 3d 20 4e 55 4c 4c | 3b 0d 09 7d 0d 09 0d 09 |c = NULL|;..}....|
|00005fd0| 69 66 20 28 66 69 6c 65 | 50 74 72 2d 3e 75 6e 64 |if (file|Ptr->und|
|00005fe0| 69 73 63 61 72 64 65 64 | 20 21 3d 20 4e 55 4c 4c |iscarded| != NULL|
|00005ff0| 29 20 7b 0d 09 09 66 72 | 65 65 20 28 66 69 6c 65 |) {...fr|ee (file|
|00006000| 50 74 72 2d 3e 75 6e 64 | 69 73 63 61 72 64 65 64 |Ptr->und|iscarded|
|00006010| 29 3b 0d 09 09 66 69 6c | 65 50 74 72 2d 3e 75 6e |);...fil|ePtr->un|
|00006020| 64 69 73 63 61 72 64 65 | 64 20 3d 20 4e 55 4c 4c |discarde|d = NULL|
|00006030| 3b 0d 09 7d 0d 0d 09 69 | 66 20 28 66 69 6c 65 50 |;..}...i|f (fileP|
|00006040| 74 72 2d 3e 72 65 61 6c | 69 6e 64 65 78 65 73 20 |tr->real|indexes |
|00006050| 21 3d 20 4e 55 4c 4c 29 | 20 7b 0d 09 09 66 72 65 |!= NULL)| {...fre|
|00006060| 65 20 28 66 69 6c 65 50 | 74 72 2d 3e 72 65 61 6c |e (fileP|tr->real|
|00006070| 69 6e 64 65 78 65 73 29 | 3b 0d 09 09 66 69 6c 65 |indexes)|;...file|
|00006080| 50 74 72 2d 3e 72 65 61 | 6c 69 6e 64 65 78 65 73 |Ptr->rea|lindexes|
|00006090| 20 3d 20 4e 55 4c 4c 3b | 0d 09 7d 0d 0d 09 69 66 | = NULL;|..}...if|
|000060a0| 20 28 66 69 6c 65 50 74 | 72 2d 3e 63 68 61 6e 67 | (filePt|r->chang|
|000060b0| 65 64 5f 66 6c 61 67 20 | 21 3d 20 4e 55 4c 4c 29 |ed_flag |!= NULL)|
|000060c0| 20 7b 0d 09 09 66 72 65 | 65 20 28 2d 2d 66 69 6c | {...fre|e (--fil|
|000060d0| 65 50 74 72 2d 3e 63 68 | 61 6e 67 65 64 5f 66 6c |ePtr->ch|anged_fl|
|000060e0| 61 67 29 3b 0d 09 09 66 | 69 6c 65 50 74 72 2d 3e |ag);...f|ilePtr->|
|000060f0| 63 68 61 6e 67 65 64 5f | 66 6c 61 67 20 3d 20 4e |changed_|flag = N|
|00006100| 55 4c 4c 3b 0d 09 7d 0d | 0d 09 69 66 20 28 66 69 |ULL;..}.|..if (fi|
|00006110| 6c 65 50 74 72 2d 3e 65 | 71 75 69 76 73 20 21 3d |lePtr->e|quivs !=|
|00006120| 20 4e 55 4c 4c 29 20 7b | 0d 09 09 66 72 65 65 20 | NULL) {|...free |
|00006130| 28 66 69 6c 65 50 74 72 | 2d 3e 65 71 75 69 76 73 |(filePtr|->equivs|
|00006140| 29 3b 0d 09 09 66 69 6c | 65 50 74 72 2d 3e 65 71 |);...fil|ePtr->eq|
|00006150| 75 69 76 73 20 3d 20 4e | 55 4c 4c 3b 0d 09 7d 0d |uivs = N|ULL;..}.|
|00006160| 0d 09 69 66 20 28 66 69 | 6c 65 50 74 72 2d 3e 62 |..if (fi|lePtr->b|
|00006170| 75 66 66 65 72 20 21 3d | 20 4e 55 4c 4c 29 20 7b |uffer !=| NULL) {|
|00006180| 0d 09 09 66 72 65 65 20 | 28 66 69 6c 65 50 74 72 |...free |(filePtr|
|00006190| 2d 3e 62 75 66 66 65 72 | 29 3b 0d 09 09 66 69 6c |->buffer|);...fil|
|000061a0| 65 50 74 72 2d 3e 62 75 | 66 66 65 72 20 3d 20 4e |ePtr->bu|ffer = N|
|000061b0| 55 4c 4c 3b 0d 09 7d 0d | 0d 09 69 66 20 28 66 69 |ULL;..}.|..if (fi|
|000061c0| 6c 65 50 74 72 2d 3e 6c | 69 6e 62 75 66 20 21 3d |lePtr->l|inbuf !=|
|000061d0| 20 4e 55 4c 4c 29 20 7b | 0d 09 09 66 72 65 65 20 | NULL) {|...free |
|000061e0| 28 66 69 6c 65 50 74 72 | 2d 3e 6c 69 6e 62 75 66 |(filePtr|->linbuf|
|000061f0| 29 3b 0d 09 09 66 69 6c | 65 50 74 72 2d 3e 6c 69 |);...fil|ePtr->li|
|00006200| 6e 62 75 66 20 3d 20 4e | 55 4c 4c 3b 0d 09 7d 0d |nbuf = N|ULL;..}.|
|00006210| 0d 09 73 63 72 69 70 74 | 50 74 72 20 3d 20 66 69 |..script|Ptr = fi|
|00006220| 6c 65 50 74 72 2d 3e 73 | 63 72 69 70 74 50 74 72 |lePtr->s|criptPtr|
|00006230| 3b 0d 09 77 68 69 6c 65 | 20 28 73 63 72 69 70 74 |;..while| (script|
|00006240| 50 74 72 20 21 3d 20 4e | 55 4c 4c 29 20 7b 0d 09 |Ptr != N|ULL) {..|
|00006250| 09 6e 65 78 74 53 63 72 | 69 70 74 50 74 72 20 3d |.nextScr|iptPtr =|
|00006260| 20 73 63 72 69 70 74 50 | 74 72 2d 3e 6c 69 6e 6b | scriptP|tr->link|
|00006270| 3b 0d 09 09 66 72 65 65 | 20 28 73 63 72 69 70 74 |;...free| (script|
|00006280| 50 74 72 29 3b 0d 09 09 | 73 63 72 69 70 74 50 74 |Ptr);...|scriptPt|
|00006290| 72 20 3d 20 6e 65 78 74 | 53 63 72 69 70 74 50 74 |r = next|ScriptPt|
|000062a0| 72 3b 0d 09 7d 0d 09 66 | 69 6c 65 50 74 72 2d 3e |r;..}..f|ilePtr->|
|000062b0| 73 63 72 69 70 74 50 74 | 72 20 3d 20 4e 55 4c 4c |scriptPt|r = NULL|
|000062c0| 3b 0d 7d 0d 0d 2f 2a 20 | 41 64 6a 75 73 74 20 69 |;.}../* |Adjust i|
|000062d0| 6e 73 65 72 74 73 2f 64 | 65 6c 65 74 65 73 20 6f |nserts/d|eletes o|
|000062e0| 66 20 62 6c 61 6e 6b 20 | 6c 69 6e 65 73 20 74 6f |f blank |lines to|
|000062f0| 20 6a 6f 69 6e 20 63 68 | 61 6e 67 65 73 0d 09 20 | join ch|anges.. |
|00006300| 61 73 20 6d 75 63 68 20 | 61 73 20 70 6f 73 73 69 |as much |as possi|
|00006310| 62 6c 65 2e 0d 0d 09 20 | 57 65 20 64 6f 20 73 6f |ble.... |We do so|
|00006320| 6d 65 74 68 69 6e 67 20 | 77 68 65 6e 20 61 20 72 |mething |when a r|
|00006330| 75 6e 20 6f 66 20 63 68 | 61 6e 67 65 64 20 6c 69 |un of ch|anged li|
|00006340| 6e 65 73 20 69 6e 63 6c | 75 64 65 20 61 20 62 6c |nes incl|ude a bl|
|00006350| 61 6e 6b 0d 09 20 6c 69 | 6e 65 20 61 74 20 6f 6e |ank.. li|ne at on|
|00006360| 65 20 65 6e 64 20 61 6e | 64 20 68 61 76 65 20 61 |e end an|d have a|
|00006370| 6e 20 65 78 63 6c 75 64 | 65 64 20 62 6c 61 6e 6b |n exclud|ed blank|
|00006380| 20 6c 69 6e 65 20 61 74 | 20 74 68 65 20 6f 74 68 | line at| the oth|
|00006390| 65 72 2e 0d 09 20 57 65 | 20 61 72 65 20 66 72 65 |er... We| are fre|
|000063a0| 65 20 74 6f 20 63 68 6f | 6f 73 65 20 77 68 69 63 |e to cho|ose whic|
|000063b0| 68 20 62 6c 61 6e 6b 20 | 6c 69 6e 65 20 69 73 20 |h blank |line is |
|000063c0| 69 6e 63 6c 75 64 65 64 | 2e 0d 09 20 60 63 6f 6d |included|... `com|
|000063d0| 70 61 72 65 73 65 71 27 | 20 61 6c 77 61 79 73 20 |pareseq'| always |
|000063e0| 63 68 6f 6f 73 65 73 20 | 74 68 65 20 6f 6e 65 20 |chooses |the one |
|000063f0| 61 74 20 74 68 65 20 62 | 65 67 69 6e 6e 69 6e 67 |at the b|eginning|
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.